POJ2991–Crane(成段更新+向量旋转)

题目大意

有一个为N节的机械手，每次可以让某个关节点旋转到某一角度，问旋转操作结束之后最末端节点的坐标

题解

当第i段与第i+1段之间的关节进行旋转时，从第i+1段到第n段都要进行旋转，类似于成段更新（成段旋转），如果把每个线段看成一个向量的话，末端的坐标等于所有向量的和。已知某个点的坐标（x,y)，求逆时针旋转之后的坐标:

或

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 100005
#define lson l,m,s<<1
#define rson m+1,r,s<<1|1
int angle[MAXN],setv[MAXN<<2];
double sumx[MAXN<<2],sumy[MAXN<<2];
void PushUp(int s)
{
    sumx[s]=sumx[s<<1]+sumx[s<<1|1];
    sumy[s]=sumy[s<<1]+sumy[s<<1|1];
}
void build(int l,int r,int s)
{
    setv[s]=0;
    if(l==r) {
        scanf("%lf",&sumy[s]);
        sumx[s]=0;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUp(s);
}
void rotate(int s,int d)
{
    double x,y;
    double dd= (d) * acos(-1.0) / 180;
    x=sumx[s]*cos(dd)-sumy[s]*sin(dd);
    y=sumx[s]*sin(dd)+sumy[s]*cos(dd);
    sumx[s]=x;
    sumy[s]=y;
}
void PushDown(int s)
{
    if(setv[s]) {
        setv[s<<1]+=setv[s];
        setv[s<<1|1]+=setv[s];
        rotate(s<<1,setv[s]);
        rotate(s<<1|1,setv[s]);
        setv[s]=0;
    }
}
void update(int ql,int qr,int d,int l,int r,int s)
{
    if(ql<=l&&r<=qr) {
        setv[s]+=d;
        rotate(s,d);
        return;
    }
    PushDown(s);
    int m=(l+r)>>1;
    if(ql<=m) update(ql,qr,d,lson);
    if(qr>m) update(ql,qr,d,rson);
    PushUp(s);
}
int main(void)
{
    int t,n;
    bool first=false;
    while(scanf("%d%d",&n,&t)!=EOF) {
        if(first)
            printf("\n");
        first=true;
        build(1,n,1);
        for(int i=1; i<=n; i++)
            angle[i]=180;
        int p,deg;
        while(t--) {
            scanf("%d%d",&p,&deg);
            update(p+1,n,deg-angle[p],1,n,1);
            angle[p]=deg;
            printf("%.2lf %.2lf\n",sumx[1],sumy[1]);
        }
    }
    return 0;
}