作者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)