Crane /// 向量旋转+线段树

题目大意：

给定n条首尾相接的线段的长度

第一条从0,0开始，所有线段垂直与x轴向上延伸

给定c次操作 每次操作给定 s,a

使得 由第s条线段的角度 逆时针旋转a后 达到第s+1条线段的角度

每次操作后输出最后一条线段末尾端点的坐标

向量逆时针旋转公式为

x' = x * cos(A) - y * sin(A); y' = x * sin(A) + y * cos(A);

一个向量  (x,y)  可分解两个向量为 垂直于y轴的(x,0) 和垂直于x轴的 (0,y)

两个分向量逆时针A度后

(x',0) = ( x*coa(A),x*sin(A) )   (0,y') = ( -y*sin(A),y*cos(A) )

两个旋转后的分向量 再合并就可得到旋转后的 (x',y')

用线段树维护一段区间内由 该区间内第一段线段的起点 指向 最后一段线段的末尾的向量

每次操作更新区间时 我们只对 操作位置处于当前区间的左子区间 的区间更新

那么这样当更新一段区间时 当前向量=左子区间的向量+右子区间旋转后的的向量

并且对于区间长度为1的区间不做处理

#include <bits/stdc++.h>

using namespace std;

const double PI=acos(-1.0);

const int N=;

int n,c,L[N];

double pre[N];

double angT[N<<];

double x[N<<],y[N<<];

void build(int k,int l,int r) {

    angT[k]=x[k]=0.0;

    if(r==l) y[k]=L[l];

    else {

        int lson=k*, rson=k*+;

        int m=(l+r)/;

        build(lson,l,m);

        build(rson,m+,r);

        y[k]=y[lson]+y[rson];

    }

}

void change(int s,double ang,int k,int l,int r) {

    if(s<l || l==r) return; // 操作位置不在范围内 或 区间长度为1 不作处理

    else if(s<=r) {

        int lson=k*, rson=k*+;

        int m=(l+r)/;

        change(s,ang,lson,l,m);

        change(s,ang,rson,m+,r); // 先处理左右子区间

        if(s<=m) angT[k]+=ang; // 操作位置位于区间的左子区间内 可根据左右子区间的向量更新

        double sina=sin(angT[k]), cosa=cos(angT[k]);

        x[k]=x[lson]+(x[rson]*cosa-y[rson]*sina);

        y[k]=y[lson]+(x[rson]*sina+y[rson]*cosa);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&c)) {

        for(int i=;i<=n;i++) {

            scanf("%d",&L[i]);

            pre[i]=PI;

        }

        build(,,n);

        while(c--) {

            int s,a; scanf("%d%d",&s,&a);

            double ang=(double)a/180.0*PI;

            change(s,ang-pre[s],,,n);

            pre[s]=ang; // 要求改变为a度 考虑之前已改变过

            printf("%.2f %.2f\n",x[],y[]);

        }

        printf("\n");

    }

    return ;

}