P3454 [POI 2007] OSI-Axes of Symmetry 题解

lzh0220 · 2025-04-07 20:56:30 · 题解

题意

给你一个多边形，问你这个多边形有几条对称轴。

思路

考虑轴对称的图形有什么共性。

随意画一个轴对称图形，将它的一条对称轴画出，观察两边翻折后完全一样，这非常像一个回文序列的形式。

于是有了一个比较基础的思路：将每条边的长度和每个角的角度求出来，组成一个长度为 2n 的环，在环上操作。

考虑将环变成链，那我们就可以在这个链上使用 manacher 求出每个位置的最长回文串长度。如果这个长度大于等于 n，那么就说明该位置有一条对称轴。

最后答案由于会被统计两遍，因此要除以 2。

时间复杂度 O(n)。

code

signed main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
        for(int i=1;i<=n-1;i++)lst[i]=a[i+1]-a[i];
        lst[n]=a[1]-a[n];
        for(int i=1;i<=n;i++)a[i]=lst[i];
        for(int i=1;i<=n-1;i++){
            lst[i*2-1]=Dot{length(a[i]),0};
            lst[i*2]=Dot{dot(a[i],a[i+1])/length(a[i])/length(a[i+1]),cross(a[i],a[i+1])/length(a[i])/length(a[i+1])};
        }
        lst[n*2-1]=Dot{length(a[n]),0};
        lst[n*2]=Dot{dot(a[n],a[1])/length(a[n])/length(a[1]),cross(a[n],a[1])/length(a[n])/length(a[1])};
        for(int i=1;i<=n*2;i++)lst[i+n*2]=lst[i];
        memset(ans,0,sizeof(ans));manacher(4*n);
        int tot=0;
        for(int i=n+1;i<=3*n;i++)if(ans[i]>=n)tot++;
        cout<<tot/2<<endl;
    }
}