BZOJ 1100: [POI2007]对称轴osi

1100: [POI2007]对称轴osi

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 630  Solved: 243
[Submit][Status][Discuss]

Description

FGD小朋友——一个闻名遐迩的年轻数学家——有一个小MM，yours。FGD小朋友非常喜欢他的MM，所以他很乐
意帮助他的MM做数学作业。但是，就像所有科学的容器一样，FGD的大脑拒绝不停地重复思考同样的问题。不幸的
是，yours是一个十分用功的学生，所以她不停地让FGD帮助她检查她的作业。一个阳光明媚的周末，yours的数学
老师布置了非常多的寻找多边形的对称轴的题，足够她做相当长的一段时间了。在此之前FGD已经决定去海边度过
这个难得的假期，不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地，他找到了解决方案，最好写一个
程序来帮助yours检查她的数学作业。因为FGD并非一个计算机科学家，所以他找到了他的好朋友你，请你帮助他完
成这个任务。请写一个程序：读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出

Input

　　输入的第一行包含一个正整数t(1<=t<=10)，为多边形的边数。接下来，为t个多边形的描述，每个描述的第一
行为一个正整数n(3<=n<=100000)，表示了多边形的点数。然后在后面n行每行两个整数x和y(?100000000<=x, y<=1
00000000)，依次表示多边形的顶点坐标。多边形不一定是凸的，但是不自交——任何两条边都只有最多一个公共
点——他们的公共端点。此外，没有两条连续的边平行。

Output

　　你的程序应该输出正好t行，第k行包含了一个整数nk——表示第k个多边形有多少个对称轴。

Sample Input

2
12
1 -1
2 -1
2 1
1 1
1 2
-1 2
-1 1
-2 1
-2 -1
-1 -1
-1 -2
1 -2
6
-1 1
-2 0
-1 -1
1 -1
2 0
1 1

Sample Output

4
2

HINT

Source

[Submit][Status][Discuss]

分析

概括：求多边形对称轴数，O(边数)。

远看计算几何，近看字符串处理，2333~~~

考虑如果能够把多边形用字符串表示出来，对称就可以翻译为回文。

然后选择用每条边的长度和两条临边的叉积表示角度，即可翻译成字符串。

代码

 #include <bits/stdc++.h>

 template <class Int>
 inline Int sqr(const Int &num) {
     return num * num;
 }

 template <class Int>
 inline Int min(const Int &a, const Int &b) {
     return a < b ? a : b;
 }

 const int maxn = ;

 int n;
 int cas;
 int len;
 int x[maxn];
 int y[maxn];
 int s[maxn];
 int r[maxn];

 inline int calc1(int mid) {
     int left = (mid -  + n) % n;
     int right = (mid +  + n) % n;
     return
         (x[left] - x[mid]) * (y[mid] - y[right])
     -    (y[left] - y[mid]) * (x[mid] - x[right]);
 }

 inline int calc2(int left) {
     int right = (left +  + n) % n;
     return
         sqr(x[left] - x[right])
     +    sqr(y[left] - y[right]);
 }

 signed main(void) {
     scanf("%d", &cas);
     while (cas--) {
         scanf("%d", &n);
         for (int i = ; i < n; ++i)
             scanf("%d%d", x + i, y + i);
         memset(s, , sizeof(s));
         for (int i = ; i < n; ++i) {
             s[i << ] = calc1(i);
             s[i <<  | ] = calc2(i);
         }
         len = n << ;
         for (int i = ; i < n; ++i)
             s[len + i] = s[i];
         len = n << ;
         int maxi = , id = , answer = ;
         for (int i = ; i < len; ++i) {
             if (maxi > i)
                 r[i] = min(r[*id - i], maxi - i);
             else
                 r[i] = ;
             while (i - r[i] >=  && i + r[i] <= len
             && s[i - r[i]] == s[i + r[i]])++r[i];
             if (maxi < i + r[i])
                 maxi = i + r[i], id = i;
             if (r[i] > n)++answer;
         }
         printf("%d\n", answer);
     }
 }

BZOJ_1100.cpp

@Author: YouSiki