BZOJ1100【POI2007】对称轴osi

Problem

【POI2007】对称轴osi


Description

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

Input

输入的第一行包含一个正整数 ,为多边形的边数。
接下来,为 个多边形的描述。
每个描述的第一行为一个正整数 ,表示了多边形的点数。
后面 行每行两个整数 ,依次表示多边形的顶点坐标。
多边形不一定是凸的,但是不自交。任何两条边都只有最多一个公共点,即它们的公共端点。此外,没有两条连续的边平行。

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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

1
2
4
2

标签:Manacher

Solution

好题。

如果我们确定一个多边形的每条边和每个角,我们就确定了这个多边形。那么半个多边形呢?也是一样的。
我们将 边形写成长为 的数组,即每条边的长度和两边夹角的叉积交错排列。将这个数组看成一个环,对称意味着这个环关于某个位置对称。按常理断环成链后跑 ,过程中判每个位置的回文半径是否大于 即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, nxt[MAX_N+5], s[MAX_N+5]; bool mrk[26];
int main() {
read(n);
for (int i = 0; i < n; i++) read(nxt[i]), nxt[i] = i-nxt[i];
for (int p = 1; p < n; p++) {
if (~nxt[p]) s[p] = s[nxt[p]];
else {
memset(mrk, false, sizeof mrk);
for (int q = nxt[p-1]; ~q; q = nxt[q])
mrk[s[q+1]] = true;
for (int c = 1; c < 26; c++)
if (!mrk[c]) {s[p] = c; break;}
}
}
for (int i = 0; i < n; i++) printf("%c", 'a'+s[i]);
return 0;
}
------------- Thanks For Reading -------------
0%