【hdu 5533】【2015 ACM/ICPCアジアエリア長春駅】Dancing Strson Me題意＆題解＆コード
テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5533 n点の座標を与えてこれらの点が正n辺形を構成できるかを問う.データ範囲が小さいので、n<=100、私達は暴力的に1つの点と他のすべての点の距離を算出することができます.正n辺形を構成するため、図を描いたら、1つの点と一番近い点は必ず辺につながっています.正の多角形の辺の長さは同じですので、直接列挙して判断すればいいです.コード:
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
using namespace std;
int n,T,x[105],y[105],cnt;
double dis[105][105];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for (int i=1;i<=n;i++)
for (int j=i+1;j<=n;j++)
{
int lx=abs(x[j]-x[i]);
int ly=abs(y[j]-y[i]);
double xx=(double)lx*1.0;
double yy=(double)ly*1.0;
dis[i][j]=sqrt(xx*xx+yy*yy);
dis[j][i]=dis[i][j];
}
int flag=0;
for (int i=1;i<=n;i++)
{
cnt=0;
double mmin=99999.9;
for (int j=1;j<=n;j++)
{
if (i==j) continue;
if (dis[i][j]<mmin)
{
cnt=1;
mmin=dis[i][j];
}
else if (dis[i][j]==mmin)
cnt++;
}
if (cnt<2)
{printf("NO
");flag=1;break;}
}
if (!flag)
printf("YES
");
}
}