题意:给出一个多边形的N个点的坐标,求这个多边形的重心。


1、质量集中在顶点上:

n个顶点坐标为(xi,yi),质量为mi,则重心 :

X = ∑( xi×mi ) / ∑mi  

Y = ∑( yi×mi ) / ∑mi  

若每个点的质量相同,则有

X = ∑xi / n  

Y = ∑yi / n 


2、质量分布均匀:  

质量均匀的三角形重心:  

X = ( x0 + x1 + x2 ) / 3  

Y = ( y0 + y1 + y2 ) / 3   


3、计算三角形面积的公式:

向量乘积:S=1/2*a*b(这是公式,但是在这个题目中除以和不除以2甚至除以4都是对的,因为在计算中会被约掉,但是除大了会GG)


题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1115


代码:


Memory: 1936 KB
Time: 62 MS
Language: C++
Result: Accepted
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAX 1000010
#define y0 yy
int n, m;
double x, y, s, t, x0, y0;
struct Node{
    double x, y;
}node[MAX];
double get_area(double x1, double y1, double x2, double y2){
    return (x1*y2-y1*x2)/2;
}
int main()
{
    cin>>n;
    while(n--){
        cin>>m;
        x=y=s=t=0;
        for(int i=0;i<m;i++)cin>>node[i].x>>node[i].y;
        x0 = node[0].x;y0=node[0].y;
        for(int i=1;i<m-1;i++){
            t = get_area(node[i].x-x0, node[i].y-y0, node[i+1].x-x0, node[i+1].y-y0);
            s+=t;
            x+=(node[i].x+node[i+1].x+x0)*t;
            y+=(node[i].y+node[i+1].y+y0)*t;
        }
        printf("%.2lf %.2lf\n", x/(3.0*s), y/(3.0*s));
    }
    return 0;
}