http://www.zybbs.org/JudgeOnline/problem.php?id=1100
這個題乍一看是計算幾何題，其實吧……
首先我們需要知道一個結(jié)論：一個軸對稱圖形旋轉(zhuǎn)小于180的角，能夠跟自己恰好重合k次，則該圖形有k個對稱軸。
那么這個題的難點就是，如何找到圖形的中心進行旋轉(zhuǎn)。中心是很難找的（至少我不會），所以我們需要一些特殊的方法……
軸對稱圖形還有的性質(zhì)就是：任意一點沿對稱軸翻折能與另一點重合，任意一條邊也是如此。
那么我們是否可以通過點和邊得特征來判斷是不是重合呢？答案是肯定的。
這樣我們就可以用一個數(shù)組來記錄點和邊的特征，這樣題目就由幾何問題轉(zhuǎn)化成為匹配問題。
記錄點是沒有意義的，因為我們不能找中心。我們可以記錄邊的長度。
但是題目說“不保證是凸多邊形”，所以我們還需要判斷一下點的折向，可以求一下叉積。
#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;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
