PKU 2991: Crane

セグメント木の練習です.

一つの角が変化すると, それ以降のクレーンの位置も全て変更するため, セグメント木を使い, 区間ごとに処理をしていくのが最適でしょう.

区間[i, j]には, 始点i, 終点jのベクトルの情報をもたせます.

#include <stdio.h>
#include <math.h>

#define INF (100000000)
#define ST_SIZE (1 << 15)

int n, c;
int L[10000];
double vx[ST_SIZE], vy[ST_SIZE], ang[ST_SIZE];
double prev[ST_SIZE];

// それぞれの区間に対応したそれぞれのベクトルのy成分を求める.
void init(int k, int l, int r)
{
    ang[k] = vx[k] = 0.0;
    
    if (r - l == 1){
        vy[k] = L[l];
    }
    else {
        int chl = k * 2 + 1, chr = k * 2 + 2;
        init(chl, l, (l + r) / 2);
        init(chr, (l + r) / 2, r);
        vy[k] = vy[chl] + vy[chr];
    }
}


//s : 変更する場所 a : 変更する角度 v : 注目している節 l : 左 r : 右
void change(int s, double a, int v, int l, int r)
{
    //そもそもsが区間内に無いんだったら, 更新する必要は無い.
    if (s <= l){
        return;
    }
    //rについても同じく.
    else if (s < r){
        int chl = v * 2 + 1, chr = v * 2 + 2;
        int m = (l + r) / 2;
        
        change(s, a, chl, l, m);
        change(s, a, chr, m, r);
        
        //sが区間の中央より大きかったらそこの角を大きくする必要は無い.
        if (s <= m){
            ang[v] += a;
        }
        
        vx[v] = vx[chl] + (cos(ang[v]) * vx[chr] - sin(ang[v]) * vy[chr]);
        vy[v] = vy[chl] + (sin(ang[v]) * vx[chr] + cos(ang[v]) * vy[chr]);
    }
}

int main(void)
{
    int i;
    int S, A;
    double a;
    int flag;
    
    flag = 0;
    while(~scanf("%d%d", &n, &c)){
        
        for (i = 0; i < n; i++){
            scanf("%d", &L[i]);
        }
        
        init(0, 0, n);
        for (i = 1; i < n; i++){
            prev[i] = M_PI;
        }
        
        if (flag){
            printf("\n");
        }
        for (i = 0; i < c; i++){
            scanf("%d%d", &S, &A);
            a = A * M_PI / 180.0;
            
            change(S, a - prev[S], 0, 0, n);
            prev[S] = a;
            printf("%.2f %.2f\n", vx[0], vy[0]);
            flag = 1;
        }
    }
    return (0);
}