Blast the Enemy! UVALive - 4426 

题意: 求任意多边形重心

思路:

重心的横坐标=sigma(三角形重心x * Stot) / Stot

重心的纵坐标=sigma(三角形重心y * Stot) / Stot

其中三角形的重心x=(x[i]+x[j]+x[k])/3;

其中三角形的重心y=(y[i]+y[j]+y[k])/3;

其中Stot代表多边形总面积

#include<cstdio>
#include<vector>
#include<cmath>
#include<string>
#include<string.h>
#include<iostream>
#include<algorithm>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5;
const int MOD=1e9+7;
const double eps=1e-15;
int sign(double x){
    return abs(x)<eps? 0 : x<0?-1:1;
}
struct Point{
    double x,y;
    Point(double x=0.0,double y=0.0):x(x),y(y){}
    Point operator -(const Point &rhs)const{
        return Point(x-rhs.x,y-rhs.y);
    }
};
typedef Point Vector;
double cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}
Point p[N];
int ks;
int main(void){
    int n;
    while(scanf("%d",&n)==1){
        if(!n)  break;
        for(int i=0;i<n;i++){
            double x,y;
            scanf("%lf%lf",&x,&y);
            p[i]={x,y};
        }
        double sumx=0.0,sumy=0.0,area=0.0;
        for(int i=1;i<n-1;i++){
            double t=cross(p[i]-p[0],p[i+1]-p[0])/2;
            area+=t;
            sumx+=(p[0].x+p[i].x+p[i+1].x)/3*t;
            sumy+=(p[0].y+p[i].y+p[i+1].y)/3*t;
        }
        printf("Stage #%d: %.6f %.6f\n",++ks,sumx/area,sumy/area);
    }
    return 0;
}