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~~~

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

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

代码

 1 #include <bits/stdc++.h>
 2 
 3 template <class Int> 
 4 inline Int sqr(const Int &num) {
 5     return num * num;
 6 }
 7 
 8 template <class Int> 
 9 inline Int min(const Int &a, const Int &b) {
10     return a < b ? a : b;
11 }
12 
13 const int maxn = 800005;
14 
15 int n;
16 int cas;
17 int len;
18 int x[maxn];
19 int y[maxn];
20 int s[maxn];
21 int r[maxn];
22 
23 inline int calc1(int mid) {
24     int left = (mid - 1 + n) % n;
25     int right = (mid + 1 + n) % n;
26     return 
27         (x[left] - x[mid]) * (y[mid] - y[right])
28     -    (y[left] - y[mid]) * (x[mid] - x[right]);
29 }
30 
31 inline int calc2(int left) {
32     int right = (left + 1 + n) % n;
33     return 
34         sqr(x[left] - x[right])
35     +    sqr(y[left] - y[right]);
36 }
37 
38 signed main(void) {
39     scanf("%d", &cas);
40     while (cas--) {
41         scanf("%d", &n);
42         for (int i = 0; i < n; ++i)
43             scanf("%d%d", x + i, y + i);
44         memset(s, 0, sizeof(s));
45         for (int i = 0; i < n; ++i) {
46             s[i << 1] = calc1(i);
47             s[i << 1 | 1] = calc2(i);
48         }
49         len = n << 1;
50         for (int i = 0; i < n; ++i)
51             s[len + i] = s[i];
52         len = n << 2;
53         int maxi = 0, id = 0, answer = 0;
54         for (int i = 0; i < len; ++i) {
55             if (maxi > i)
56                 r[i] = min(r[2*id - i], maxi - i);
57             else
58                 r[i] = 1;
59             while (i - r[i] >= 0 && i + r[i] <= len
60             && s[i - r[i]] == s[i + r[i]])++r[i];
61             if (maxi < i + r[i])
62                 maxi = i + r[i], id = i;
63             if (r[i] > n)++answer;
64         }
65         printf("%d
", answer);
66     }
67 }

BZOJ_1100.cpp

@Author: YouSiki