Algoogle

Algorithm for Programming Contest

AOJ 2526 Pie Chart is as easy as pie.

Category: AOJ Tag: geometry

Pie Chart is as easy as pie.

問題概要


解法


割合が与えられるので, 最初に中心, 扇の角2つを出す.
この3点からもとの扇型の三角形部分の面積を出して扇形から引く.
次に中心を移動後の点に変えた三角形を足せば移動後の面積が出る.
ただし中心点が弦と弧の間(凹んだ形の扇型)だったらはじめの三角形の面積は足す.
移動後の点が弦と弧の間だったらあとの三角形は引く.
この2つの判定はccwですればよい.

コード


(2526.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i = 0;i < (a); i++)
#define PI acos(-1.0)
typedef complex<double> P;

int r, x, y, n, sum;
P prev, moved;
double prevang, movedang;

inline double cross(const P& a, const P& b) { return imag(conj(a)*b); }
inline double dot(const P& a, const P& b) { return real(conj(a)*b); }

int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if (cross(b, c) > 0)   return +1;       // +1 : 反時計回り
    if (cross(b, c) < 0)   return -1;       // -1 : 時計回り
    if (dot(b, c) < 0)     return +2;       // +2 : 線上(c--a--b)
    if (norm(b) < norm(c)) return -2;       // -2 : 線上(a--b--c)
    return 0;
}

int calc(int rate){
    double cirArea = 1.0 * rate / 100 *  r * r *  PI;
    P s = prev;
    double sang = prevang;
    double tang = sang - 1.0 * rate / 50 * PI;
    prevang = tang;
    P t = s * polar(1.0,tang-sang);
    prev = t;
    double bArea = abs(s.real() * t.imag() - s.imag() * t.real()) / 2;
    P ts = s - moved;
    P tt = t - moved;
    double aArea = abs(ts.real() * tt.imag() - ts.imag() * tt.real()) / 2;

    if(ccw(s,t,P(0,0)) == 1) bArea *= -1;
    if(ccw(s,t,moved) == 1) aArea *= -1;
    return (int)(abs(cirArea - bArea + aArea) / cirArea * 100);
}

int main(){
    sum = 0;
    cin >> r >> x >> y >> n;
    moved = P(x,y);
    prev = P(0,100);
    prevang = PI / 2;
    rep(i,n){
        int rate;
        cin >> rate;
        cout << calc(rate) << (i==n-1? '\n': ' ');
        sum += rate;
    }
    return 0;
}

Comments