http://www.zybbs.org/JudgeOnline/problem.php?id=1100
这个题乍一看是计算几何题，其实吧……
首先我们需要知道一个结论：一个轴对称图形旋转小于180的角，能够跟自己恰好重合k次，则该图形有k个对称轴。
那么这个题的难点就是，如何找到图形的中心进行旋转。中心是很难找的（至少我不会），所以我们需要一些特殊的方法……
轴对称图形还有的性质就是：任意一点沿对称轴翻折能与另一点重合，任意一条边也是如此。
那么我们是否可以通过点和边得特征来判断是不是重合呢？答案是肯定的。
这样我们就可以用一个数组来记录点和边的特征，这样题目就由几何问题转化成为匹配问题。
记录点是没有意义的，因为我们不能找中心。我们可以记录边的长度。
但是题目说“不保证是凸多边形”，所以我们还需要判断一下点的折向，可以求一下叉积。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define mn 200005
#define sqr(x) ((x)*(x))
using namespace std;
int Cases,n,tot,ans,x[mn],y[mn],pattern[mn],match[mn<<1],next[mn<<1];
int main(){
scanf("%d",&Cases);
while(Cases--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&x[i],&y[i]);
x[n+1]=x[1],y[n+1]=y[1],x[n+2]=x[2],y[n+2]=y[2];
tot=0,ans=0;
for(int i=1;i<=n;i++){
match[++tot]=sqr(x[i+1]-x[i])+sqr(y[i+1]-y[i]);
match[++tot]=(x[i+1]-x[i])*(y[i+2]-y[i])-(y[i+1]-y[i])*(x[i+2]-x[i]);
}
for(int i=1;i<=tot;i++)
pattern[tot-i+1]=match[i+tot]=match[i];
memset(next,0,sizeof(next));
for(int i=2,j=0;i<=tot;i++){
while(j && pattern[j+1]!=pattern[i]) j=next[j];
next[i]=(j+=(pattern[j+1]==pattern[i]));
}
for(int i=1,j=0;i<=(tot<<1);i++){
while(j && pattern[j+1]!=match[i]) j=next[j];
j+=(pattern[j+1]==match[i]);
if(j==tot) ans++,j=next[j];
}
printf("%d\n",ans);
}
return 0;
}
