专栏文章

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

llzh0220
P3454题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipopl26
此快照首次捕获于
2025/12/03 15:27
3 个月前
此快照最后确认于
2025/12/03 15:27
3 个月前
查看原文

题意

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

思路

考虑轴对称的图形有什么共性。
随意画一个轴对称图形，将它的一条对称轴画出，观察两边翻折后完全一样，这非常像一个回文序列的形式。
于是有了一个比较基础的思路：将每条边的长度和每个角的角度求出来，组成一个长度为 2n2n 的环，在环上操作。
考虑将环变成链，那我们就可以在这个链上使用 manacher 求出每个位置的最长回文串长度。如果这个长度大于等于 nn，那么就说明该位置有一条对称轴。
最后答案由于会被统计两遍，因此要除以 22。
时间复杂度 O(n)O(n)。

code

CPP
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;
	}
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...