多边形重心模板
#include <iostream>#include <cmath>#include <iomanip>using namespace std;
struct point{double x;double y;};
//求多边形的重心算法//说明://求多边形重心并不是简单的把求三角形的重心公式推广就行了//我的算法是在平面上取一点(一般取原点, 这样可以减少很多计算, 而且使思路更清晰^_^)//这样就得到了N个三角形OP[i]P[i+1](其中点的顺序要为逆时针的),//分别求出这N个三角形的重心Ci和面积Ai(注意此处面积是又向面积, 就是用叉乘求面积时保留其正负号)//在求出A = A1+A2+…+AN(同样保留正负号的代数相加)//最终重心C = sigma(Ai+Ci)/A;point gravity(point *p, int n){double area = 0;point center;center.x = 0;center.y = 0;
for (int i = 0; i < n-1; i++){ area += (p[i].x*p[i+1].y – p[i+1].x*p[i].y)/2; center.x += (p[i].x*p[i+1].y – p[i+1].x*p[i].y) * (p[i].x + p[i+1].x); center.y += (p[i].x*p[i+1].y – p[i+1].x*p[i].y) * (p[i].y + p[i+1].y);}
area += (p[n-1].x*p[0].y – p[0].x*p[n-1].y)/2;center.x += (p[n-1].x*p[0].y – p[0].x*p[n-1].y) * (p[n-1].x + p[0].x);center.y += (p[n-1].x*p[0].y – p[0].x*p[n-1].y) * (p[n-1].y + p[0].y);
center.x /= 6*area;center.y /= 6*area;
return center;}
，我想去旅行，一个人背包，一个人旅行，
