首页 > 代码库 > NYOJ3(多边形重心)

NYOJ3(多边形重心)

题目意思:
在某个多边形上,取n个点,这n个点顺序给出,按照给出顺序将相邻的点用直线连接, (第一个和最后一个连接),所有线段不和其他线段相交,但是可以重合,可得到一个多边形或一条线段或一个多边形和一个线段的连接后的图形;

如果是一条线段,我们定义面积为0,重心坐标为(0,0).现在求给出的点集组成的图形的面积和重心横纵坐标的和。

http://acm.nyist.net/JudgeOnline/problem.php?pid=3

输入
第一行有一个整数0<n<11,表示有n组数据;
每组数据第一行有一个整数m<10000,表示有这个多边形有m个顶点;
输出
输出每个多边形的面积、重心横纵坐标的和,小数点后保留三位;
样例输入
3
3
0 1
0 2
0 3
3
1 1
0 0
0 1
4
1 1
0 0
0 0.5
0 1
样例输出
0.000 0.000
0.500 1.000
0.500 1.000
题目分析:

此题是一个多边形重心问题,直接上模板进行了,只是不知道为什么将多边形分成在n个点中任选一个点分成n-2个三角形求解问什么过不了,最后以原点为中心进行划分反而过了?下面贴上AC代码。


AC代码:

/**
 *①质量集中在顶点上
 *  n个顶点坐标为(xi,yi),质量为mi,则重心
 * X = ∑( xi×mi ) / ∑mi
 * Y = ∑( yi×mi ) / ∑mi
 * 特殊地,若每个点的质量相同,则
 * X = ∑xi / n
 * Y = ∑yi / n
 *②质量分布均匀
 * 特殊地,质量均匀的三角形重心:
 * X = ( x0 + x1 + x2 ) / 3
 * Y = ( y0 + y1 + y2 ) / 3
 *③三角形面积公式:S =  ( (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1) ) / 2 ;
 *做题步骤:1、将多边形分割成n-2个三角形,根据③公式求每个三角形面积。
 *            2、根据②求每个三角形重心。
 *            3、根据①求得多边形重心。
**/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
struct Point{
 double x,y;
}p[10005];
double Area(Point p1,Point p2,Point p3){//叉乘求三角形面积
    return ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))/2.0;
}
int main()
{
    int n,t;
    Point p0;
    p0.x=p0.y=0.0;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        double gx,gy,sumarea,area;
        gx=gy=sumarea=0;
        for(int i = 0; i < n; ++i)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        for(int i=1;i<=n;i++){
            area=Area(p0,p[i%n],p[i-1]);//与原点单个三角的面积
            gx+=(p[i%n].x+p[i-1].x)*area;//重心乘以其权值(面积),因为每一个都要除以3,所医院放在最后
            gy+=(p[i%n].y+p[i-1].y)*area;
            sumarea+=area;//计算所有权值
        }

        if(sumarea < 0.0000001 && sumarea >-0.0000001){
            printf("0.000 0.000\n");
            continue;
        }
        /**
        gx=gx/(sumarea*3);//求的多边形重心
        gy=gy/(sumarea*3);
        **/
        printf("%.3lf %.3lf\n",sumarea,(gx+gy)/(sumarea*3));
        //printf("%.2lf %.2lf\n",gx,gy);
    }
    return 0;
}


NYOJ3(多边形重心)