首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。