多边形重心

例题：hdu 1115

给出一堆点，求多边形的重心。

我们可以把多边形划分为许多三角形。三角形的重心很简单：

x = ( x1 + x2 + x3 ) / 3 , y = ( y1 + y2 + y3 ) / 3

多边形的重心公式为：

借用大佬博客的图片：https://blog.csdn.net/u010499449/article/details/38168677

公式当中的行列式，其实就是三角形的面积，我们可以利用叉积来求。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+10;
int T,n;
double s,resx,resy;
struct node{double x,y;}t[N];
inline double corss(node a,node b,node c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%d",&n); resx=resy=s=0;
		for(int i=1;i<=n;i++)	scanf("%lf %lf",&t[i].x,&t[i].y);
		for(int i=3;i<=n;i++){
			double ts=corss(t[1],t[i-1],t[i])/2;
			resx+=(t[1].x+t[i-1].x+t[i].x)*ts;
			resy+=(t[1].y+t[i-1].y+t[i].y)*ts;
			s+=ts;
		}
		printf("%.2lf %.2lf\n",resx/s/3,resy/s/3);
	}
	return 0;
}