###背景
送分的题目总是要有的。
###描述
给出两个多边形,请判断它们之中哪个更接近圆形。 每个人对“接近圆形”的定义或许会不同,所以可以参考下面的样例来确定判断标准。数据保证,如果将所表示的图形画出来,能让人立刻直观地判断出“谁更圆”。
###输入格式
输入文件第一行为一个整数T,表明一共有T组数据。
每组数据的第一行为两个整数 n1 和 n2 ,表示两个多边形的边数。
第二行为 n1 对实数,每对实数(x,y)表示了第一个多边形的每个顶点。
第三行为 n2 对实数,每对实数(x,y)表示了第二个多边形的每个顶点。
顶点按照顺序给出,并且保证多边形不自交。
###输出格式
输出T行,每行一个整数。输出1代表第一个多边形更圆,而2代表第二个多边形更圆。请不要输出空格等其他字符。
###样例输入
3
3 4
1732 -1000 0 2000 -1732 -1000
1000 1000 1000 -1000 -1000 -1000 -1000 1000
4 4
1000 0 0 100 -1000 0 0 -100
1000 0 0 200 -1000 0 0 -200
6 6
1000 1000 0 500 -1000 1000 -1000 -1000 0 -500 1000 -1000
1000 1000 0 1500 -1000 1000 -1000 -1000 0 -1500 1000 -1000
###样例输出
2
2
2
###数据范围与约定
第1个测试点满足:所有的多边形都可以近似看做正多边形。
第2个测试点满足:每一组的两个多边形边数相同,且其中一个可以近似看做正多边形。
第3个和第4个输入文件满足:每组数据当中,要么两个多边形都是正多边形,要么两个多边形边数相同且其中一个是正多边形。
第5个和第6个输入文件满足: n1=n2=3 。
第7个和第8个输入文件满足: n1,n2≤1000 。
第9个和第10个输入文件没有特殊的特征。
所有的输入满足:T=10, 3≤n1,n2≤30,000 ,|x|,|y|≤10,000,且如果将所表示的图形画出来,能让人立刻直观地判断出“谁更圆”。
###样例解释
第一组数据大体上为一个正三角形和一个正方形,显然正方形更接近圆。
第二组数据为两个菱形,显然后者更接近圆。
第三组数据为两个六边形,显然后者更接近圆。
###评分标准
对于所有数据,除样例外,T=10。
由于对于“接近圆形”的定义或许会不同,只要你的输出有90%以上是正确的,即输出的前10行有至少9行是正确的,就得该测试点的满分。
###来源
原创
###下面是我的做法
首先求出两个多边形的重心,求多边形顶点到重心,距离的方差,方差小的更像圆(对于大部分的点)
若方差接近,则顶点多的更像圆(对于只有正多边形的点)
AC-Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct Dot{double x,y;}D1[30005],D2[30005];
//double Dis1[30005],Dis2[30005];
inline double Dist(Dot a,Dot b)
{
return (sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)));
}
inline double Area(Dot a,Dot b,Dot c)
{
double ret=0;
ret=a.x*b.y+b.x*c.y+c.x*a.y-b.x*a.y-c.x*b.y-a.x*c.y;
return ret/2;
}
double Abs(double x)
{
return (x<0)?(-x):(x);
}
void work()
{
int n1,n2;
double sum_x1=0,sum_y1=0,sum_area1=0,area=0;
double sum_x2=0,sum_y2=0,sum_area2=0;
double totDist1=0,totDist2=0;
double S1=0,S2=0;
scanf("%d%d",&n1,&n2);
scanf("%lf%lf",&D1[0].x,&D1[0].y);
scanf("%lf%lf",&D1[1].x,&D1[1].y);
for (int i=2;i<n1;i++)
{
scanf("%lf%lf",&D1[i].x,&D1[i].y);
area=Area(D1[0],D1[i-1],D1[i]);
sum_area1+=area;
sum_x1+=(D1[0].x+D1[i-1].x+D1[i].x)*area;
sum_y1+=(D1[0].y+D1[i-1].y+D1[i].y)*area;
}
sum_x1=sum_x1/sum_area1/3;
sum_y1=sum_y1/sum_area1/3;
D1[n1].x=sum_x1;D1[n1].y=sum_y1;
//--2
scanf("%lf%lf",&D2[0].x,&D2[0].y);
scanf("%lf%lf",&D2[1].x,&D2[1].y);
for (int i=2;i<n2;i++)
{
scanf("%lf%lf",&D2[i].x,&D2[i].y);
area=Area(D2[0],D2[i-1],D2[i]);
sum_area2+=area;
sum_x2+=(D2[0].x+D2[i-1].x+D2[i].x)*area;
sum_y2+=(D2[0].y+D2[i-1].y+D2[i].y)*area;
}
sum_x2=sum_x2/sum_area2/3;
sum_y2=sum_y2/sum_area2/3;
D2[n2].x=sum_x2;D2[n2].y=sum_y2;
//--STEP2
for (int i=0;i<n1;i++)
totDist1+=Dist(D1[n1],D1[i]);
for (int i=0;i<n2;i++)
totDist2+=Dist(D2[n2],D2[i]);
totDist1/=n1;totDist2/=n2;
//--STEP3
for (int i=0;i<n1;i++)
S1+=pow(totDist1-Dist(D1[n1],D1[i]),2);
for (int i=0;i<n2;i++)
S2+=pow(totDist2-Dist(D2[n2],D2[i]),2);
S1=sqrt(S1)/n1;S2=sqrt(S2)/n2;
//--ANSWER IT!
if (Abs(S1-S2)<10)
printf("%d\n",1+(n1<n2));
else
printf("%d\n",1+(S1>S2));
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
work();
return 0;
}