AOJ 1292 Top Spinning

問題

線分と円弧からなる図形が与えられる。
この図形の重心の座標、および重心が図形の内部にあるかどうかを求めよ。

制約条件

図形をつくる線分と円弧の数の和は100以下
誤差は10^-3以下でなければならない

方針

誤差がかなりゆるいので、円弧を折れ線で近似して良い。
1000分割くらいしたら問題なく通った。

多角形の重心は公式を使う。（ライブラリ化しておくべきだった）

ソースコード

P center(const G &p){
    int n = p.size();
    double a = 0;
    double cx = 0, cy = 0;
    rep(i, n){
        a += p[i].real() * p[(i + 1) % n].imag() - p[(i + 1) % n].real() * p[i].imag();
        cx += (p[i].real() + p[(i + 1) % n].real())
            * (p[i].real() * p[(i + 1) % n].imag() - p[(i + 1) % n].real() * p[i].imag());
        cy += (p[i].imag() + p[(i + 1) % n].imag())
            * (p[i].real() * p[(i + 1) % n].imag() - p[(i + 1) % n].real() * p[i].imag());
    }
    a *= 0.5;
    cx /= 6 * a;
    cy /= 6 * a;
    return P(cx, cy);
}
 
const int SPLIT = 1000;
 
int main(){
    string cmd;
    while(cin >> cmd, cmd != "end"){
        G poly;
        double x, y, r;
        cin >> x >> y;
        poly.pb(P(x, y));
        while(cin >> cmd, cmd != "close"){
            if(cmd == "line"){
                cin >> x >> y;
                poly.pb(P(x, y));
            }
            else if(cmd == "arc"){
                cin >> x >> y >> r;
                 
                P cur = poly.back(), nxt(x, y);
                P dir = nxt - cur, m = (cur + nxt) * 0.5;
                double d = abs(dir);
                dir *= sqrt(r * r - d * d / 4) / d;
                if(r < 0) dir *= P(0, 1);
                else dir *= P(0, -1);
                 
                m += dir;
                double a = arg(cur - m), b = arg(nxt - m);
                if(a < 0) a += 2 * PI;
                if(b < 0) b += 2 * PI;
                if(r < 0 && a > b) b += 2 * PI;
                if(r > 0 && a < b) a += 2 * PI;
                 
                for(int i = 1; i <= SPLIT; i++){
                    double t = (i * b + (SPLIT - i) * a) / SPLIT;
                    poly.pb(m + abs(r) * P(cos(t), sin(t)));
                }
            }
            else assert(0);
        }
        P g = center(poly);
        printf("%.9f %.9f ", g.real(), g.imag());
        if(contains(poly, g) != OUT) cout << "+" << endl;
        else cout << "-" << endl;
    }
    return 0;
}