poj 2991 Crane

#include<stdio.h> #include<math.h> #include<string.h> #define PI acos(-1.0) #define N 10011 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 double sx[N<<2],sy[N<<2]; int sd[N<<2],degree[N]; void pushup(int rt) { sx[rt]=sx[rt<<1]+sx[rt<<1|1]; sy[rt]=sy[rt<<1]+sy[rt<<1|1]; } void rotate(int rt,int sd) { double d,x,y; d=sd*asin(1.0)/90.0; x=cos(d)*sx[rt]-sin(d)*sy[rt]; y=sin(d)*sx[rt]+cos(d)*sy[rt]; sx[rt]=x; sy[rt]=y; } void pushdown(int rt) { rotate(rt<<1,sd[rt]); rotate(rt<<1|1,sd[rt]); sd[rt<<1]+=sd[rt]; sd[rt<<1|1]+=sd[rt]; sd[rt]=0; } void build(int l,int r,int rt) { int m; sd[rt]=0; if(l==r) { scanf("%lf",&sy[rt]); sx[rt]=0; return ; } m=(l+r)>>1; build(lson); build(rson); pushup(rt); } void update(int p,int d,int l,int r,int rt) { int m; if(p<l) { rotate(rt,d); sd[rt]+=d; return ; } if(sd[rt]) pushdown(rt); m=(l+r)>>1; if(p<m) update(p,d,lson); update(p,d,rson); pushup(rt); } int main(void) { int i,j,n,m,flag=0; while(~scanf("%d%d",&n,&m)) { build(1,n,1); for(i=1;i<=n;i++) degree[i]=180; while(m--) { scanf("%d%d",&i,&j); update(i,j-degree[i],1,n,1); degree[i]=j; printf("%.2lf %.2lf\n",sx[1],sy[1]); } printf("\n"); } }