[POI2007]对称轴Axes of Symmetry-osi 计算几何+KMP

思路:

网上的题解也有很多了,主要介绍一下我得到的姿势.

我们抽象出边和点的信息,将多边形成一个长度为\(2n\)的字符串.

然后我们考虑有多少个这个字符串的循环同构串与这个串的反串相同.每出现一个就有一个对称轴.

想想好像是挺显然的.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
 
typedef long long LL;
 
#define N 100010
 
struct Point{
    int x,y;
    inline void read(){scanf("%d%d",&x,&y);}
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
}P[N];
inline LL Cross(const Point&a,const Point&b){return(LL)a.x*b.y-(LL)a.y*b.x;}
inline LL sqr(const int&x){return(LL)x*x;}
inline LL dis2(const Point&a,const Point&b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline LL abs(const LL&x){return x<0?-x:x;}
LL seq1[N<<2],seq2[N<<1];
 
int n;
inline int f(int x){if(x<=0)return n;else if(x>n)return 1;else return x;}
 
int pre[N<<1];
int main(){
    int cas;scanf("%d",&cas);register int i,j;
    while(cas--){
        scanf("%d",&n);for(i=1;i<=n;++i)P[i].read();
        int cnt=0;for(i=1;i<=n;++i)seq1[++cnt]=Cross(P[f(i-1)]-P[i],P[i]-P[f(i+1)])|(1LL<<62),seq1[++cnt]=dis2(P[i],P[f(i+1)]);
         
        for(i=1;i<=cnt;++i)seq2[i]=seq1[cnt-i+1];
        for(i=cnt+1;i<=2*cnt;++i)seq1[i]=seq1[i-cnt];
         
        for(j=pre[1]=0,i=2;i<=cnt;++i){
            while(j&&seq2[j+1]!=seq2[i])j=pre[j];
            if(seq2[j+1]==seq2[i])++j;pre[i]=j;
        }
        int res=0;
        for(i=1,j=0;i<2*cnt;++i){
            while(j&&seq2[j+1]!=seq1[i])j=pre[j];
            if(seq2[j+1]==seq1[i])++j;if(j==cnt)++res;
        }
        printf("%d\n",res);
    }return 0;
}