HDU 1115 Lifting the Stone：多邊形重心模板題

題目

給定多邊形頂點座標（按順序），求其重心（質心）。

公式

面積 A = ½ Σ (x_i y_{i+1} - x_{i+1} y_i)
重心 Cx = (1/(6A)) Σ (x_i + x_{i+1}) * (x_i y_{i+1} - x_{i+1} y_i)
Cy = (1/(6A)) Σ (y_i + y_{i+1}) * (x_i y_{i+1} - x_{i+1} y_i)

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
struct Point { double x, y; };
Point centroid(Point p[], int n) {
    Point c = {0,0};
    double A = 0;
    for (int i = 0; i < n; i++) {
        Point p1 = p[i], p2 = p[(i+1)%n];
        double cross = p1.x * p2.y - p2.x * p1.y;
        A += cross;
        c.x += (p1.x + p2.x) * cross;
        c.y += (p1.y + p2.y) * cross;
    }
    A *= 0.5;
    c.x /= (6 * A);
    c.y /= (6 * A);
    return c;
}
int main() {
    int T, n; scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        vector p(n);
        for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
        Point c = centroid(p.data(), n);
        printf("%.2lf %.2lf\n", c.x, c.y);
    }
    return 0;
}