POJ 2991 Crane

昔蟻本読んだ時「は？？？」ってなってたところを読み返したら理解できたので書いておきます。

問題

2991 -- Crane

解法

蟻本のとおりですが, 若干説明がわかりにくいので図を載せておきます。

ある区間のクレーンの集合を左側と右側に分けることを考えます。
で, 左側と右側それぞれで,
「一番最初のクレーンが地面に対して直角に立っている」と仮定した場合の, 原点(クレーン集合が立っている地面)からクレーンの先端までのベクトルを vx, vy で表します。
あと ang と言うのがありますが, これはあるクレーンの集合を左側と右側に分けられる場合, 右側で「地面」とみなしているものが左側の「地面」の基準(これは同時に左と右両方の集合を合わせたクレーン集合の地面の基準でもある)に対してどれくらいずれているかを示しています。あとは察してください。

const double PI = 3.1415926536;
const int MAXN = 10010;
const int SEG_SIZE = (1<<15) - 1;
int N, C;
int L[MAXN];

double ang[SEG_SIZE], vx[SEG_SIZE], vy[SEG_SIZE], pre[MAXN];

void init(int k, int l, int r) {
    ang[k] = 0; vx[k] = 0;
    if (r-l == 1) {
        vy[k] = L[l];
        return;
    }
    init(2*k+1, l, (l+r)/2);
    init(2*k+2, (l+r)/2, r);
    vy[k] = vy[2*k+1] + vy[2*k+2];
}

void change(int p, double add, int k, int l, int r) {
    if (p <= l || p >= r) return;
    int m = (l+r) / 2;
    change(p, add, 2*k+1, l, m);
    change(p, add, 2*k+2, m, r);
    if (p <= m) ang[k] += add;
    int chl = 2*k+1, chr = 2*k+2;
    double s = sin(ang[k]), c = cos(ang[k]);
    vx[k] = vx[chl] + c*vx[chr]-s*vy[chr];
    vy[k] = vy[chl] + s*vx[chr]+c*vy[chr];
}

int main() {
    int cnt = 0;
    while (cin >> N >> C) {
        if (cnt != 0) printf("\n");
        cnt++;
        for (int i = 0; i < N; i++) scanf("%d", L+i);
        for (int i = 0; i <= N; i++) pre[i] = PI;
        init(0, 0, N);
        while (C--) {
            int x, y;
            scanf("%d%d", &x, &y);
            double deg = y/360. * 2 * PI;
            double add = deg-pre[x];
            change(x, add, 0, 0, N);
            pre[x] = deg;
            printf("%.2lf %.2lf\n", vx[0], vy[0]);
        }
    }
    return 0;
}