作者miname (这本书有开始却没有结束)
看板ACMCLUB
标题Re: ACM 10416
时间Mon Jan 13 02:45:05 2003
※ 引述《ledia (totally defeated)》之铭言：
: ※ 引述《miname (这本书有开始却没有结束)》之铭言：
: : 取相邻两点和相隔一点的两点作中垂线即可(可以先砍掉一半的线)
: : 我做出来是0.002s AC...不知道0.000秒的家伙怎麽写的....
: 它... 一定是偶数个点吗? @@
奇数也没关系,我的做法也是可以work...
因为我会把每个点两两平均检查是否在对称线上
检查到最後就会把奇数的那个点当成两个点平均看是否在线上...
结果...OK..
附看不懂的code以解疑虑(反正就暴力内积给她乘下去啦...)
--
#include<stdio.h>
void main()
{
int t;
int n;
int mid;
struct{
int x,y,dx,dy;
}middle;
int data[100][2];
int i,j;
int yes;
scanf("%d",&t);
for (i=0;i<t;i++)
{
yes=0;
scanf("%d",&n);
for (j=0;j<n;j++)
{
scanf("%d %d",&data[j][0],&data[j][1]);
}
for(mid=0;mid<(n+1)/2;mid++)
{
middle.x=data[mid][0]+data[(mid+n-1)%n][0];
middle.y=data[mid][1]+data[(mid+n-1)%n][1];
middle.dx=data[mid][0]-data[(mid+n-1)%n][0];
middle.dy=data[mid][1]-data[(mid+n-1)%n][1];
for(j=0;j<=n/2;j++)
{
if(((data[mid+j][0]+data[(mid-j+n-1)%n][0]-middle.x)*middle.dx+middle.dy*(data[mid+j][1]+data[(mid-j+n-1)%n][1]-middle.y))!=0)
{
break;
}
}
if(j==(int)(n/2+1))
{
yes=1;
break;
}
}
for(mid=0;mid<=(n+1)/2;mid++)
{
middle.x=data[mid+1][0]+data[(mid+n-1)%n][0];
middle.y=data[mid+1][1]+data[(mid+n-1)%n][1];
middle.dx=data[mid+1][0]-data[(mid+n-1)%n][0];
middle.dy=data[mid+1][1]-data[(mid+n-1)%n][1];
for(j=0;j<=n/2;j++)
{
if(((data[mid+j][0]+data[(mid-j+n)%n][0]-middle.x)*middle.dx+middle.dy*(data[mid+j][1]+data[(mid-j+n)%n][1]-middle.y))!=0)
{
break;
}
}
if(j==(int)(n/2+1))
{
yes=1;
break;
}
}
if(yes)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
}
}
--
※ 发信站: 批踢踢实业坊(ptt.csie.ntu.edu.tw)
◆ From: 218.187.85.106
※ 编辑: miname 来自: 218.187.85.106 (01/13 03:04)