AC日记——Crane poj 2991

POJ - 2991

思路：

　　向量旋转；

代码：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 400005

const double pi=acos(-1.0);

struct TreeNodeType {

    int l,r,R,mid,flag;

    double x,y;

    void mem()

    {

        x=,R=;

        scanf("%lf",&y);

    }

    void rotate(int R__)

    {

        double tmp_x=x,tmp_y=y,R_=R__/180.0*pi;

        x=tmp_x*cos(R_)-tmp_y*sin(R_);

        y=tmp_y*cos(R_)+tmp_x*sin(R_);

    }

};

struct TreeNodeType tree[maxn<<];

int n,m;

void build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r,tree[now].flag=;

    if(tree[now].l==tree[now].r) { tree[now].mem();return; }

    tree[now].mid=l+r>>;build(now<<,l,tree[now].mid),build(now<<|,tree[now].mid+,r);

    tree[now].x=tree[now<<].x+tree[now<<|].x,tree[now].y=tree[now<<].y+tree[now<<|].y;

}

int query(int now,int to,int x)

{

    if(tree[now].l==tree[now].r){int pos=x-tree[now].R;tree[now].R=x;return pos;}

    if(to<=tree[now].mid) return query(now<<,to,x);else return query(now<<|,to,x);

}

void updata(int now)

{

    tree[now<<].flag+=tree[now].flag,tree[now<<|].flag+=tree[now].flag;

    tree[now<<].rotate(tree[now].flag),tree[now<<|].rotate(tree[now].flag);

    tree[now].flag=;

}

void change(int now,int l,int r,int x)

{

    if(tree[now].l==l&&tree[now].r==r) {tree[now].flag+=x,tree[now].rotate(x);return;}

    if(tree[now].flag) updata(now);if(l>tree[now].mid) change(now<<|,l,r,x);

    else if(r<=tree[now].mid) change(now<<,l,r,x);

    else change(now<<,l,tree[now].mid,x),change(now<<|,tree[now].mid+,r,x);

     tree[now].x=tree[now<<].x+tree[now<<|].x,tree[now].y=tree[now<<].y+tree[now<<|].y;

}

int main()

{

    int T=;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(T++) printf("\n");

        build(,,n);int to,x;

        for(;m--;)

        {

            scanf("%d%d",&to,&x);

            change(,to+,n,query(,to+,x));

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

        }

    }

    return ;

}