求一个多边形质心(密度均匀)

将多边形分割为三角形的并，对每个三角形求重心（三角形重心即为三点坐标的平均值），然后以三角形的有向面积为权值求加权平均即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 1e2 + 5;
const double EPS = 1e-6;
double PI;
struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x, yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }

    void input(){scanf("%lf%lf", &x, &y);}
    double x, y;
};
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
Point operator +(Point lhs, Point rhs){return Point(lhs.x + rhs.x, lhs.y + rhs.y);}
Point operator -(Point lhs, Point rhs){return Point(lhs.x - rhs.x, lhs.y - rhs.y);}
Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);}
Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);}


Point point[MAXN];
int n;


double getPolygonArea(Point *point)
{
    double ret = 0.0;
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        ret += point[nxt] ^ point[i];
    }
    return ret / 2.0;
}

Point getMassCenter(Point *point)
{
    Point ans = Point(0.0, 0.0);
    double area = getPolygonArea(point);
    if(fabs(area) <= EPS) return point[0];
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        ans = ans + (point[i] + point[nxt]) * (point[nxt] ^ point[i]);
    }
    return ans / area / 6.0;
}

int main()
{
    int tcase = 0;
    while(scanf("%d", &n) && n != 0)
    {
        ++tcase;
        for(int i = 0; i < n; ++i) point[i].input();
        Point ans = getMassCenter(point);
        printf("Stage #%d: %.6lf %.6lf\n", tcase, ans.x, ans.y);
    }
}