[BZOJ1100][POI2007]对称轴osi

1100: [POI2007]对称轴osi

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 716 Solved: 279 [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

乍一看是计算几何，结果是字符串。。。

把边长和角度存起来，然后找最长回文串即可。。。

角度的话会被卡精度，所以用叉积代替

#pragma GCC optimize("O2")
#include <cstdio>
char buf[20000000], *ptr = buf - 1;
inline int readint(){
    int n = 0;
    bool flag = false;
    while(*++ptr < '0' || *ptr > '9') if(*ptr == '-') flag = true;
    while(*ptr <= '9' && *ptr >= '0') n = (n << 1) + (n << 3) + (*ptr++ & 15);
    return flag ? -n : n;
}
template <typename _Tp>
inline _Tp min_(const _Tp &a, const _Tp &b){
    return a < b ? a : b;
}
typedef long long ll;
const int maxn = 100000 + 10;
struct Poi{
    ll x, y;
    Poi(){}
    Poi(ll _x, ll _y): x(_x), y(_y){}
    Poi operator - (const Poi &a){
        return Poi(x - a.x, y - a.y);
    }
}p[maxn];
inline ll sqr(const ll &x){
    return x * x;
}
inline ll dis(const Poi &a, const Poi &b){
    return sqr(a.x - b.x) + sqr(a.y - b.y);
}
inline ll cross(const Poi &a, const Poi &b){
    return a.x * b.y - a.y * b.x;
}
int n;
ll s[maxn * 3];
int r[maxn * 3];
void work(){
    n = readint();
    for(int i = 1; i <= n; i++){
        p[i].x = readint();
        p[i].y = readint();
    }
    p[0] = p[n];
    p[n + 1] = p[1];
    for(int i = 1; i <= n; i++){
        s[i * 2 - 1] = cross(p[i - 1] - p[i], p[i + 1] - p[i]);
        s[i * 2] = dis(p[i], p[i + 1]);
    }
    int len = n + n;
    for(int i = 1; i <= n; i++)
        s[i + len] = s[i];
    len = len + n;
    int mx = 0, id = 0, ans = 0;
    for(int i = 1; i <= len; i++){
        if(mx > i) r[i] = min_(r[2 * id - i], mx - i);
        else r[i] = 1;
        while(i - r[i] > 0 && i + r[i] <= len && s[i - r[i]] == s[i + r[i]]) r[i]++;
        if(r[i] + i > mx){
            mx = r[i] + i;
            id = i;
        }
        if(r[i] > n) ans++;
    }
    printf("%d
", ans);
}
int main(){
    fread(buf, sizeof(char), sizeof(buf), stdin);
    int T = readint();
    while(T--) work();
    return 0;
}