• Source
    1. /**************************************************************
    2.   Problem: 1100
    3.   User: zrts
    4.   Language: C++
    5.   Result: Accepted
    6.   Time:2064 ms
    7.   Memory:9456 kb
    8. ****************************************************************/
    9.  
    10. #include <cstdio>
    11. #include <cstring>
    12. #include <algorithm>
    13. #include<cmath>
    14. // by zrt
    15. // problem:
    16. // 无论你在什么时候开始,重要的是开始以后就不要停止。
    17. using namespace std ;
    18. typedef long long ll ;
    19. const double eps(1e-5) ;
    20. const int inf(0x7fffffff) ;
    21. #define MAXN 100500
    22. int tt;
    23. int n;
    24. int x[MAXN],y[MAXN];
    25. int r[4*MAXN];
    26. struct N{
    27. bool type;
    28. double a;
    29. int c;
    30. friend bool operator == ( N a,N b){
    31. return a.type==b.type&&fabs(a.a-b.a)<eps&&a.c+b.c!=0;
    32. }
    33. };
    34. N a[4*MAXN];
    35. int main(){
    36. #ifdef LOCAL
    37. freopen("in.txt","r",stdin) ;
    38. freopen("out.txt","w",stdout) ;
    39. #endif
    40. scanf("%d",&tt);
    41. while(tt--){
    42. scanf("%d",&n);
    43. int ans(0);
    44. for(int i=0;i<n;i++){
    45. scanf("%d%d",&x[i],&y[i]);
    46. }
    47. for(int i=0;i<n;i++){// bian
    48. a[i<<1|1].type=1;
    49. a[i<<1|1].c=1;
    50. a[i<<1|1].a=(x[i]-x[(i+1)%n])*1LL*(x[i]-x[(i+1)%n])+(y[i]-y[(i+1)%n])*1LL*(y[i]-y[(i+1)%n]);
    51. }
    52. for(int i=0,x1,y1,x2,y2;i<n;i++){
    53. a[i<<1].type=0;
    54. x1=x[(i+1)%n]-x[i];
    55. y1=y[(i+1)%n]-y[i];
    56. x2=x[((i-1+n)%n)]-x[i];
    57. y2=y[((i-1+n)%n)]-y[i];
    58. long long sinp=x1*1LL*y2-x2*1LL*y1;
    59. if(sinp+eps>0) a[i<<1].c=1;
    60. else a[i<<1].c=-1;
    61. a[i<<1].a=fabs(sinp)/sqrt(x1*1LL*x1+y1*1LL*y1)/sqrt(x2*1LL*x2+y2*1LL*y2);
    62. }
    63. int lim=2*n;
    64. for(int i=0;i<lim;i++){
    65. a[i+lim]=a[i];
    66. }
    67. lim<<=1;
    68. int mx(-1),id(-1);
    69. for(int i=0;i<lim;i++){
    70. // printf("#%d %d %.3f\n",i,a[i].type,a[i].a);
    71. r[i]=0;
    72. if(i<mx){
    73. r[i]=min(mx-i,r[id-(i-id)]);
    74. }
    75. while(i+r[i]<lim&&i-r[i]>=0&&a[i+r[i]]==a[i-r[i]]) r[i]++;
    76. if(i+r[i]>mx){
    77. mx=i+r[i];
    78. id=i;
    79. }
    80. if((r[i]<<1)-1>n<<1){
    81. ans++;
    82. }
    83. }
    84. printf("%d\n",ans>>1);
    85. }
    86. return 0 ;
    87. }