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