PKU 3855 Blast the Enemy!

注意！求解多邊形的質心一般將其進行分解，然后用質心*面積和/總面積求得總質心
Summary

給出一個有n(n<=100)個點的簡單多邊形，求該多邊形的重心。

Solution

根據多邊形重心的定義，可以對其進行三角剖分，計算每個三角形的面積以及重心。多邊形的重心就是所有三角形的重心對面積的加權平均數，也就是說：

center.x = (cen[0].x * area[0] + cen[1].x * area[1] ..... + cen[n].x * area[n]) / totalarea

center.y = (cen[0].y * area[0] + cen[1].y * area[1] ..... + cen[n].y * area[n]) / totalarea

cen[i]代表第i個三角形的重心，三角形的重心就是：

center_of_tri.x=(p1.x+p2.x+p3.x)/3.0

center_of_tri.y=(p1.y+p2.y+p3.y)/3.0

area[i]就是第i個三角形的面積。totalarea就是多邊形的總面積。

 1#include <cstdio>
 2#include <cmath>
 3#define EPS 1e-8
 4#define N 105
 5struct POINT {
 6    double x, y;
 7    POINT() {
 8        x = y = 0;
 9    }
10    POINT(double x, double y) :
11        x(x), y(y) {
12    }
13    void get() {
14        scanf("%lf%lf", &x, &y);
15    }
16    void print() {
17        printf("%.6lf %.6lf\n", x, y);
18    }
19    POINT operator+(const POINT &p) {
20        return POINT(x + p.x, y + p.y);
21    }
22};
23POINT pl[N];
24int n;
25double cross(POINT o, POINT &a, POINT &b) {
26    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
27}
28int sgn(double x) {
29    return x < -EPS ? -1 : x > EPS;
30}
31void solve() {
32    int i;
33    double area = 0;
34    POINT ct;
35    for (i = 0; i < n; i++)
36        pl[i].get();
37    pl[i] = pl[0];
38    for (i = 0; i < n; i++) {
39        double s = cross(POINT(), pl[i], pl[i + 1]);
40        POINT t;
41        area += s;
42        t = pl[i] + pl[i + 1];
43        ct.x += s * t.x, ct.y += s * t.y;
44    }
45    ct.x = ct.x / area / 3.0, ct.y = ct.y / area / 3.0;
46    ct.print();
47}
48int main() {
49    int T = 1;
50    while (scanf("%d", &n) && n) {
51        printf("Stage #%d: ", T++);
52        solve();
53    }
54    return 0;
55}
56

posted on 2010-10-14 17:58 yzhw 閱讀(203) 評論(0)  編輯 收藏 引用 所屬分類: geometry&phycise