AOJ 2526 - Pie Chart is as easy as pie.

問題文 : Pie Chart is as easy as pie.

解法 :
中心をずらす前の図形とずらした後の図形は, 弧を結ぶ線分と, 中心から弧の端点への辺を結んでできる三角形の面積が異なるだけである. そこで, その差分をとって割合を求めればいい.

ゆえに三角形の面積はccw を使って足したり引いたりすればいいのだが, 俗に符号付き三角形と言ったりするらしい.(しらなかった.)

コード　:

#include <cstdio>
#include <cmath>
#include <vector>
 
using namespace std;
 
const double EPS = 1e-10;
 
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y){}
    Point operator - (Point p) {return (Point(x - p.x, y - p.y));}
};
 
typedef Point Vector;
 
double dot(Vector a, Vector b)
{
    return (a.x * b.x + a.y * b.y);
}
 
double cross(Vector a, Vector b)
{
    return (a.x * b.y - a.y * b.x);
}
 
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;
 
//3点の位置関係を求める
int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) > EPS) return COUNTER_CLOCKWISE;
    if (cross(a, b) < -EPS) return CLOCKWISE;
    if (dot(a, b) < -EPS) return ONLINE_BACK;
    if (dot(a, a) < dot(b, b)) return ONLINE_FRONT;
    return ON_SEGMENT;
}
 
double area(Vector a, Vector b)
{
    return (fabs(cross(a, b)) * 0.5);
}
 
int main()
{
    int r, x, y, n;
     
    scanf("%d %d %d %d", &r, &x, &y, &n);
     
    vector<Point> v;
    v.push_back(Point(0, 100));
    int sum = 0;
    int p[10];
    for (int i = 0; i < n; i++){
        scanf("%d", &p[i]);
        sum += p[i];
        if (sum != 100) v.push_back(Point(100 * sin(sum / 100.0 * 2 * M_PI), 100 * cos(sum / 100.0 * 2 * M_PI)));
    }
     
    double prev[10], diff[10];
    for (int i = 0; i < n; i++){
        prev[i] = 0.5 * 100 * 100 * (p[i] / 100.0 * 2 * M_PI);
        diff[i] = prev[i];
        double S = area(v[i], v[(i + 1) % n]);
        if (ccw(v[i], Point(0, 0), v[(i + 1) % n]) >= 0) diff[i] -= S;
        else diff[i] += S;
    }
     
    double now[10];
    for (int i = 0; i < n; i++){
        now[i] = diff[i];
        double S = area(v[i] - Point(x, y), v[(i + 1) % n] - Point(x, y));
        if (ccw(v[i], Point(x, y), v[(i + 1) % n]) >= 0) now[i] += S;
        else now[i] -= S;
    }
     
    for (int i = 0; i < n; i++) printf("%d%c", (int)(now[i] * 100 / prev[i]), " \n"[i == n - 1]);
     
    return (0);
}