計算幾何之多邊形重心

啥叫重心？

我把它抽象的了解為幾個頂點均分權重。三個點及以上才能構成一個簡單的平面多邊形，三角形是最簡單的多邊形。三角形的重心就是三個頂點均分權重。

三角形重心

通過一個三角形重心公式來看多邊形重心公式，若一個三角形有三個點，分别為（x1,y1),(x2,y2),(x3,y3)，那麼三角形的重心公式為：

x = x 1 + x 2 + x 3 3 , y = y 1 + y 2 + y 3 3 x=\frac{x1+x2+x3}{3}, y=\frac{y1+y2+y3}{3} x=3x1+x2+x3​,y=3y1+y2+y3​

每個點的橫權值相加除以3，每個縱權值相加除以3。

多邊形重心

現在我們有一個五邊形，有5個點，其中S1為三角形△ABC的面積，同理有S2，S3。

先給出它的重心公式：

x = ( x 1 + x 2 + x 3 ) s 1 + ( x 1 + x 3 + x 4 ) s 2 + ( x 1 + x 4 + x 5 ) s 3 3 ( s 1 + s 2 + s 3 ) x=\frac{(x1+x2+x3)s1+(x1+x3+x4)s2+(x1+x4+x5)s3}{3(s1+s2+s3)} x=3(s1+s2+s3)(x1+x2+x3)s1+(x1+x3+x4)s2+(x1+x4+x5)s3​

y = ( y 1 + y 2 + y 3 ) s 1 + ( y 1 + y 3 + y 4 ) s 2 + ( y 1 + y 4 + y 5 ) s 3 3 ( s 1 + s 2 + s 3 ) y=\frac{(y1+y2+y3)s1+(y1+y3+y4)s2+(y1+y4+y5)s3}{3(s1+s2+s3)} y=3(s1+s2+s3)(y1+y2+y3)s1+(y1+y3+y4)s2+(y1+y4+y5)s3​

相當于求出三個三角形的重心，再根據三角形的面積去均分權重。相同的道理，可以畫一畫六邊形，七邊形，是一樣的道理。

是以給出n邊形重心公式：

x = ∑ i = 1 n − 2 s i ∗ ( 以 s i 為 面 積 的 三 個 點 橫 坐 标 之 和 ) 3 ∑ i = 1 n − 2 s i x=\frac{ \sum_{i=1}^{n-2}s_i*(以s_i為面積的三個點橫坐标之和) }{3\sum_{i=1}^{n-2}s_i} x=3∑i=1n−2​si​∑i=1n−2​si​∗(以si​為面積的三個點橫坐标之和)​

y = ∑ i = 1 n − 2 s i ∗ ( 以 s i 為 面 積 的 三 個 點 縱 坐 标 之 和 ) 3 ∑ i = 1 n − 2 s i y=\frac{ \sum_{i=1}^{n-2}s_i*(以s_i為面積的三個點縱坐标之和) }{3\sum_{i=1}^{n-2}s_i} y=3∑i=1n−2​si​∑i=1n−2​si​∗(以si​為面積的三個點縱坐标之和)​

就是醬紫，是不是很好了解0.0

Tip:計算三角形面積最好使用叉積，海倫公式會損失太多精度。給一下三角形叉積求三角形的公式。但在計算叉積時取點要注意，一定要按逆時針連圖，順時針計算的結果是負的，友情提示，不要加絕對值（會損失精度）。假如三角形有三個點A(x1, y1), B(x2, y2), C(x3, y3)，公式為 ：

S = ( x 2 − x 1 ) ( y 3 − y 1 ) − ( y 2 − y 1 ) ( x 3 − x 1 ) 2 S=\frac{(x2-x1)(y3-y1) - (y2-y1)(x3-x1)}{2} S=2(x2−x1)(y3−y1)−(y2−y1)(x3−x1)​

這個公式是要加絕對值的，但在計算重心時，别加。

貼個題目：

hdu1115 Lifting the Stone

這題就不能加絕對值…跟着公式敲就行

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define PI 3.1415926
using namespace std;
typedef long long ll;
//叉積求面積
double getarea(double x1, double y1, double x2, double y2, double x3, double y3) {
  return ((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)) / 2;
}
int main() {
  fio
  int t, n; 
  cin >> t;
  double x1, y1, x2, y2, x3, y3, ansx, ansy, allarea, area; 
  while(t--) {
    ansx = 0; ansy = 0; allarea = 0;
     cin >> n;
     cin >> x1 >> y1 >> x2 >> y2;
     for(int i = 2; i < n; ++i) {
       cin >> x3 >> y3;
       area = getarea(x1, y1, x2, y2, x3, y3);
       cout << area << endl;
       allarea += area;
       ansx += (x1+x2+x3) * area;
       ansy += (y1+y2+y3) * area;
       x2 = x3; y2 = y3;
   }
   printf("%.2lf %.2lf\n", ansx / allarea / 3.0, ansy / allarea / 3.0);
  }
  return 0;
}