题解 P3454 【[POI2007]OSI-Axes of Symmetry】

· · 题解

Manacher做法。

考虑一个多边形的对称轴有什么性质——

明显，如果沿着对称轴的一端把整个环状的多边形裁成一条链，则链上相邻两条边的夹角，必定是回文的。

回文就直接上Manacher啦。

我们把整个多边形断环成链复制三份，然后对着复制完的多边形的所有夹角构成的串跑一遍Manacher。假如发现里面出现了一条长度 \geq n 的回文串，就意味着出现了一条对称轴。

注意，因为对称轴会在其与多边形的两个交点处被计算两遍，故最终答案应除以 2。

具体实现时，可以使用叉积判夹角相同，但实际上使用 atan2 暴力算夹角然后用 double 判相同也够用了。

代码：

#include<bits/stdc++.h>
using namespace std;
int T,n;
const double pi=acos(-1);
const double eps=1e-10;
struct Vector{
    double x,y;
    Vector(double X=0,double Y=0){x=X,y=Y;}
    friend Vector operator +(const Vector &u,const Vector &v){return Vector(u.x+v.x,u.y+v.y);}
    friend Vector operator -(const Vector &u,const Vector &v){return Vector(u.x-v.x,u.y-v.y);}
    friend Vector operator *(const Vector &u,const double &v){return Vector(u.x*v,u.y*v);}
    friend Vector operator /(const Vector &u,const double &v){return Vector(u.x/v,u.y/v);}
    friend double operator &(const Vector &u,const Vector &v){return u.x*v.y-u.y*v.x;}//cross times
    friend double operator |(const Vector &u,const Vector &v){return u.x*v.x+u.y*v.y;}//point times
    double operator ~()const{return sqrt(x*x+y*y);}//the modulo of a vector
    double operator !()const{return atan2(y,x);}//the angle of a vector
    void read(){scanf("%lf%lf",&x,&y);}
}p[300100];
int m;
double ang[600100];
int Centre,Rpos,rad[600100];
double FMOD(double ip){
    if(ip<0)ip+=2*pi;
    if(ip>=2*pi)ip-=2*pi;
    return ip;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n),m=0;
        for(int i=1;i<=n;i++)p[i].read(),p[n+i]=p[2*n+i]=p[i];
        p[0]=p[n],p[3*n+1]=p[1];
        ang[++m]=-1;
        for(int i=1;i<=3*n;i++){
            ang[++m]=FMOD(!(p[i+1]-p[i])-!(p[i]-p[i-1]));
            ang[++m]=-1;
        }
        Centre=Rpos=0;
        for(int i=1;i<=m;i++){
            rad[i]=(i<Rpos)?min(Rpos-i,rad[Centre*2-i]):1;
            while(i+rad[i]<=m&&i-rad[i]>=1)if(fabs(ang[i+rad[i]]-ang[i-rad[i]])<eps)rad[i]++;else break;
            if(i+rad[i]>Rpos)Rpos=i+rad[i],Centre=i;
        }
        int res=0;
        for(int i=2*n+1;i<=4*n;i++)res+=(rad[i]>=n);
        printf("%d\n",res>>1);
    }
    return 0;
}