首页 > 代码库 > AC日记——Crane poj 2991

AC日记——Crane poj 2991

POJ - 2991

 

 

思路:

  向量旋转;

 

代码:

#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define maxn 400005const double pi=acos(-1.0);struct TreeNodeType {    int l,r,R,mid,flag;        double x,y;        void mem()    {        x=0,R=180;        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<<2];int n,m;void build(int now,int l,int r){    tree[now].l=l,tree[now].r=r,tree[now].flag=0;    if(tree[now].l==tree[now].r) { tree[now].mem();return; }    tree[now].mid=l+r>>1;build(now<<1,l,tree[now].mid),build(now<<1|1,tree[now].mid+1,r);    tree[now].x=tree[now<<1].x+tree[now<<1|1].x,tree[now].y=tree[now<<1].y+tree[now<<1|1].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<<1,to,x);else return query(now<<1|1,to,x);}void updata(int now){    tree[now<<1].flag+=tree[now].flag,tree[now<<1|1].flag+=tree[now].flag;    tree[now<<1].rotate(tree[now].flag),tree[now<<1|1].rotate(tree[now].flag);    tree[now].flag=0;}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<<1|1,l,r,x);    else if(r<=tree[now].mid) change(now<<1,l,r,x);    else change(now<<1,l,tree[now].mid,x),change(now<<1|1,tree[now].mid+1,r,x);     tree[now].x=tree[now<<1].x+tree[now<<1|1].x,tree[now].y=tree[now<<1].y+tree[now<<1|1].y;}int main(){    int T=0;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(T++) printf("\n");        build(1,1,n);int to,x;        for(;m--;)        {            scanf("%d%d",&to,&x);            change(1,to+1,n,query(1,to+1,x));            printf("%.2lf %.2lf\n",tree[1].x,tree[1].y);        }    }    return 0;}

 

AC日记——Crane poj 2991