Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 601 Accepted Submission(s):
320
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#define MAX 10010
#define INF 0x3f3f3f
#define DD double
using namespace std;
DD f(DD x1,DD y1,DD x2,DD y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main()
{
int t,n,m,j,i,k;
DD x[MAX],y[MAX];
DD s[MAX];
int vis[MAX];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
int k=0;
memset(vis,0,sizeof(vis));
DD Min;
int next=1;
int ans=1;
for(i=1;i<=n;i++)
{
Min=INF;
for(j=1;j<=n;j++)
{
if(next==j) continue;
//如果自己到自己就跳过
else if(!vis[j])
{
if(Min>f(x[next],y[next],x[j],y[j]))
{
Min=f(x[next],y[next],x[j],y[j]);
//找距离next点最近的点
ans=j;
}
}
}
next=ans; //找到下一个点
vis[next]=1;
s[k++]=Min;
}
int flag=1;
for(i=0;i<k-1;i++)
{
if(s[i]!=s[i+1])
{
flag=0;
break;
}
}
if(s[0]!=s[k-1])
flag=0;
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/5031025.html