【多边形重心/新增三角形叉积公式】HDU 1115 Lifting the Stone
http://acm.hdu.edu.cn/showproblem.php?pid=1115
题意：逆时针给出n个点，求这个n边形的重心
Sample Input
2
4
5 0
0 5
-5 0
0 -5
4
1 1
11 1
11 11
1 11
Sample Output
0.00 0.00
6.00 6.00
求三角形面积公式【已知三个顶点坐标】
逆时针依次为(x1,y1),(x2,y2),(x3,y3)：S为正
顺时针S为负
所谓三角形的重心就是三角形的外心，即中线交点，如图，重心坐标为(xg,yg)
求多边形重心的题目大致有这么几种：
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、质量分布不均匀
只能用函数多重积分来算，不太会
这题的做法：
将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，则面积就是质量】
因为质量都集中在重心
所以把所有求出来的重心按逆时针连接起来又是一个多边形
但是这个多边形的质量集中在顶点上
所以可以利用上面公式进行计算
#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>//#include <map>#include <queue>#include <utility>#include <iomanip>#include <stack>#include <list>#include <vector>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>//#include <ctime>#include <ctype.h>using namespace std;struct point{double x, y;}p[1000005];double area (point a, point b, point c) //叉积公式求三角形面积的2倍{return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;}int main(){int t, n, i;point pre;double gx, gy, sum, m, x1, y1;scanf ("%d", &t);while (t--){sum = gx = gy = 0;scanf ("%d", &n);for (i = 0; i < n; i++)scanf ("%lf%lf", &p[i].x, &p[i].y);pre = p[1];for (i = 2; i < n; i++){m = area (p[0], pre, p[i]); //设密度=2，质量=2*面积，加绝对值fabs会错，因为可能有凹边形，产生负面积...x1 = (p[0].x + pre.x + p[i].x) / 3;y1 = (p[0].y + pre.y + p[i].y) / 3; //三角形重心坐标gx += m * x1; //公式中的 ∑( xi×mi )gy += m * y1; //公式中的 ∑( yi×mi )sum += m; //公式中的 ∑mipre = p[i];}gx /= sum, gy /= sum;printf ("%.2lf %.2lf\n", gx, gy);}return 0;}