首页 > 代码库 > BZOJ1100: [POI2007]对称轴osi

BZOJ1100: [POI2007]对称轴osi

1100: [POI2007]对称轴osi

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 334  Solved: 130
[Submit][Status]

Description

FGD小朋友——一个闻名遐迩的年轻数学家——有一个小MM,yours。FGD小朋友非常喜欢他的MM,所以他很乐意帮助他的MM做数学作业。但是,就像所有科学的容器一样,FGD的大脑拒绝不停地重复思考同样的问题。不幸的是,yours是一个十分用功的学生,所以她不停地让FGD帮助她检查她的作业。一个阳光明媚的周末,yours的数学老师布置了非常多的寻找多边形的对称轴的题,足够她做相当长的一段时间了。在此之前FGD已经决定去海边度过这个难得的假期,不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地,他找到了解决方案,最好写一个程序来帮助yours检查她的数学作业。因为FGD并非一个计算机科学家,所以他找到了他的好朋友你,请你帮助他完成这个任务。请写一个程序:读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出

Input

输入的第一行包含一个正整数t(1<=t<=10),为多边形的边数。接下来,为t个多边形的描述,每个描述的第一行为一个正整数n(3<=n<=100000),表示了多边形的点数。然后在后面n行每行两个整数x和y(−100000000<=x, y<=100000000),依次表示多边形的顶点坐标。多边形不一定是凸的,但是不自交——任何两条边都只有最多一个公共点——他们的公共端点。此外,没有两条连续的边平行。

Output

你的程序应该输出正好t行,第k行包含了一个整数nk——表示第k个多边形有多少个对称轴。

Sample Input

2
12
1 -1
2 -1
2 1
1 1
1 2
-1 2
-1 1
-2 1
-2 -1
-1 -1
-1 -2
1 -2
6
-1 1
-2 0
-1 -1
1 -1
2 0
1 1

Sample Output

4
2

HINT

 

 

Source

题解:

有意思的题目。计算几何的味道如此浓厚,最后却用的是字符串算法来解决。

话说我对于计算几何真是一窍不通T_T

搬运wyx528的题解:

考虑求一个多边形有多少条对称轴,我们可以把多边形表示成一个由边长和角度组成的序列,这样如果两个
点的连线 i 和 j 是一条对称轴的话,那么这两个点分割成的两个序列连起来应该是一个回文串。具体方法就是我
们找一个长度为 2n 的序列,第一个是边长,第二个是角度,第三个是边长,依次类推。记得到的这个串为 S,
我们复制 S 得到 SS,及 S 的反串为 S’,则原问题就变成了 S’在 SS 中出现了多少次,这个可以用 kmp 解决。注意
如果角度会挂精度的话可以直接用叉积来代替,因为如果边长不等的话肯定就不行了,如果边长相等的话叉积不
等,就说明了角度不等。

 

后面这一部分也可以直接上manacher,不用实数又没精度误差又好写,orz

代码:一些解释写在注释里

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100000+1014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 #define sqr(x) (x)*(x)24 using namespace std;25 inline ll read()26 {27     ll x=0,f=1;char ch=getchar();28     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}29     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();}30     return x*f;31 }32 int n,cs,lim,ans,mx,id,p[4*maxn];33 struct rec{ll x,y;}b[maxn];34 struct rec235 {36    bool type;//表示该点的属性,是角还是边 37    ll x;38    friend bool operator ==(rec2 a,rec2 b)39    {40        return a.type==b.type&&a.x==b.x;41    }42 }a[4*maxn];43 inline ll dist(rec a,rec b)//距离的平方 44 {45     return sqr(a.x-b.x)+sqr(a.y-b.y);46 }47 inline ll cross(rec a,rec b,rec c)//叉积 48 {49     return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);50 }51 int main()52 {53     freopen("input.txt","r",stdin);54     freopen("output.txt","w",stdout);55     cs=read();56     while(cs--)57     {58         n=read();59         for0(i,n-1)b[i].x=read(),b[i].y=read();60         for0(i,n-1)61          {62              a[i<<1|1].type=1;63              a[i<<1|1].x=dist(b[i],b[(i+1)%n]);64          }65         for0(i,n-1)66          {67             a[i<<1].type=0;68             a[i<<1].x=cross(b[i],b[(i-1+n)%n],b[(i+1)%n]);69          }70         lim=n<<1; 71         for0(i,lim-1)a[i+lim]=a[i];//将原串赋值一遍 72         lim<<=1;73         mx=id=0;memset(p,0,sizeof(p));74         for0(i,lim-1) 75          {76              if(mx>i)p[i]=min(p[2*id-i],mx-i);77              for(;i-p[i]>=0,i+p[i]<lim,a[i-p[i]]==a[i+p[i]];p[i]++)78              if(i+p[i]>mx){mx=i+p[i];id=i;}79          }//manacher 80         ans=0; 81         for0(i,lim-1)if(p[i]-1>=n)ans++;//每条对称轴有两个顶点 82         printf("%d\n",ans>>1); 83     }        84     return 0;85 }
View Code

 

BZOJ1100: [POI2007]对称轴osi