poj2991(Crane)线段树+计算几何

2 1
10 5
1 90

3 2
5 5 5
1 270
2 90

5.00 10.00

-10.00 5.00
-5.00 10.00

题意：n根相连的木棍初始时竖直摆放，从下到上编号依次为1~n。给出每根木棍长度和c次操作。每次操作两个操作数s和a，表示转动s+1，使得s和s+1夹角变为a，其中夹角指的是s逆时针转到s+1转过的角度。输出每次操作之后最后一根木棍尾端点坐标，其中原点为第一根木棍头端点。

题解：记录第s根棍子到第s+1根棍子间的逆时针角度prv[s],这样每次输入a时就能确定第s+1根及以后棍子的绝对旋转角度，然后用这个角度维护区间值。对于一个向量(x, y)，它逆时针旋转A度后，得到的新向量为：x' = xcos(A) - ysin(A)，y' = xsin(A) + ycos(A)。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

const double PI = acos(-1.0);
const int st_size = (1 << 15) - 1;
const int maxn = 10010;

//输入
int n, c;
int L[maxn];

//线段树维护的数据
double vx[st_size], vy[st_size];    //各节点的向量
double ang[st_size];    //各节点的角度

double prv[maxn];

//初始化线段树
//k是节点的编号，l, r表示当前节点对应的是[l, r]区间
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和s+1的角度变为a
//v是节点的编号，l, r表示当前节点对应的是[l, r)区间
void change(int s, double a, int v, int l, int r)
{
    if (s <= l)
        return;
    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);
        if (s <= m)
            ang[v] += a;
        double si = sin(ang[v]), co = cos(ang[v]);
        vx[v] = vx[chl] + co * vx[chr] - si * vy[chr];
        vy[v] = vy[chl] + si * vx[chr] + co * vy[chr];
    }
}

int main()
{
    int cnt = 0;
    while (~scanf("%d%d", &n, &c))
    {
        if (cnt++)
            printf("\n");
        for (int i = 0; i < n; ++i)
            scanf("%d", &L[i]);

        //初始化
        init(0, 0, n);
        fill(prv+1, prv+n, PI);

        while (c--)
        {
            int s;
            double a;
            scanf("%d%lf", &s, &a);
            a = a / 180.0 * PI;   //把角度换算成弧度
            change(s, a-prv[s], 0, 0, n);
            prv[s] = a;
            printf("%.2f %.2f\n", vx[0], vy[0]);
        }
    }
    return 0;
}