題意：給一個(gè) $n$ 個(gè)點(diǎn)的多邊形，求對稱軸個(gè)數(shù)。

$n\le 10^5$

顯然對稱軸一定在頂點(diǎn)或邊的中點(diǎn)上。

但你 $n^2$ 枚舉完全沒有一點(diǎn)能過的樣子。

冷靜分析，發(fā)現(xiàn)有 “中點(diǎn)”，“對稱軸”，很自然個(gè)鬼地想到了manacher。

在邊的中點(diǎn)插入一個(gè)點(diǎn)，然后復(fù)制一遍斷環(huán)成鏈。 然后跑馬拉車，擴(kuò)展的時(shí)候判斷是否軸對稱。

設(shè)點(diǎn) $i$ 可以擴(kuò)展到 $[i?p_i,i+p_i]$，如果擴(kuò)展到整個(gè)多邊形就是合法的對稱軸，即 $2p_i+1\ge 2n$，$p_i\ge n$，并且只有第一圈的點(diǎn)會有貢獻(xiàn)。一個(gè)對稱軸會算兩次，除以 $2$ 就是答案。

方便實(shí)現(xiàn)的小trick：

邊界的地方隨機(jī)一個(gè)點(diǎn)就不用特判。

判軸對稱可以算出中點(diǎn)，用叉積判在不在已知的對稱軸上。如果對稱軸未確定就設(shè)成 $0$ 向量。但要注意本來就確定的時(shí)候要特判一下不要把它改回零向量。

讀入的坐標(biāo)都乘上 $4$，就可以不用 double。

復(fù)雜度 $O(n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #define MAXN 400005 using namespace std; inline int read() {int ans=0,f=1;char c=getchar();while (!isdigit(c)) (c=='-')&&(f=-1),c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return f*ans; } typedef long long ll; int x[MAXN],y[MAXN]; int p[MAXN],maxr,mid,cnt; int lasx,lasy; inline bool check(int l,int i,int r) {if ((ll)(x[l]-x[i])*(x[l]-x[i])+(ll)(y[l]-y[i])*(y[l]-y[i])!=(ll)(x[r]-x[i])*(x[r]-x[i])+(ll)(y[r]-y[i])*(y[r]-y[i]))return false;int tx=(x[l]+x[r])/2-x[i],ty=(y[l]+y[r])/2-y[i];if ((ll)tx*lasy!=(ll)ty*lasx) return false;if ((ll)tx*tx+(ll)ty*ty) lasx=tx,lasy=ty;return true; } int main() {for (int T=read();T;T--){int n=read();for (int i=1;i<=2*n;i+=2) x[i]=read()*4,y[i]=read()*4;for (int i=2*n+1;i<=4*n;i+=2) x[i]=x[i-2*n],y[i]=y[i-2*n];x[4*n+1]=x[1],y[4*n+1]=y[1];for (int i=2;i<=4*n;i+=2) x[i]=(x[i-1]+x[i+1])/2,y[i]=(y[i-1]+y[i+1])/2;x[0]=rand(),y[0]=rand(),x[4*n+1]=rand(),y[4*n+1]=rand();maxr=mid=cnt=0;for (int i=1;i<=4*n;i++){if (i<maxr) p[i]=min(p[2*mid-i],maxr-i);else p[i]=0;lasx=lasy=0;while (check(i-p[i]-1,i,i+p[i]+1)) ++p[i];if (i+p[i]>maxr) maxr=i+p[i],mid=i;cnt+=(p[i]>=n);}printf("%d\n",cnt/2);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【POI2007】OSI-Axes of Symmetry【计算几何】【manacher】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。