Rounder

Posted on By 二价氢

###背景

送分的题目总是要有的。

###描述

给出两个多边形,请判断它们之中哪个更接近圆形。 每个人对“接近圆形”的定义或许会不同,所以可以参考下面的样例来确定判断标准。数据保证,如果将所表示的图形画出来,能让人立刻直观地判断出“谁更圆”。

###输入格式

输入文件第一行为一个整数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;
}