首页 > 代码库 > 线段树 poj 2991
线段树 poj 2991
我们只要把这些向量求和,最终所指的位置就是终点,因此我们只要维护好向量的区间和就可以了。对于第二个问题,我们可以用一个数组degree[i]表示第i个向量和第i-1一个向量当前的夹角,这样就有了当前的状态,每次读入操作后就会方便的得到相当于进行旋转多少角度的操作了,然后再更新一下degree[i]即可。并且我们每读入一个操作只会影响一个degree[]的值,不会影响到其他的degree[]。
总而言之,我们要把每个线段看成一个向量,并维护这些向量的区间和,同时要实现对区间中每个元素都加上一个值这一操作。
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; #define MAXN 10010 const double pi =acos(-1.0); int z[MAXN],deg[MAXN],re[MAXN<<3]; struct node { int l,r; double x,y; }x[MAXN<<3]; double getrad(int a) { return a*pi/180; } void Build(int l,int r,int a) { x[a].l=l; x[a].r=r; x[a].x=0; x[a].y=z[r]-z[l-1]; re[a]=0; if(l==r) return ; int mid=(l+r)>>1; Build(l,mid,a<<1); Build(mid+1,r,a<<1|1); } void Rotate(double &dx,double &dy,double rad) { double x=dx,y=dy; dx=x*cos(rad)-y*sin(rad); dy=x*sin(rad)+y*cos(rad); } void push_down(int a) { double rad=getrad(re[a]); int ls=a<<1,rs=a<<1|1; if(re[a]) { re[ls]+=re[a]; re[rs]+=re[a]; Rotate(x[ls].x,x[ls].y,rad); Rotate(x[rs].x,x[rs].y,rad); re[a]=0; } } void push_up(int a) { x[a].x=x[a<<1].x+x[a<<1|1].x; x[a].y=x[a<<1].y+x[a<<1|1].y; } void update(int l,int r,int a1,int w,int a) { double rad=getrad(w); if(l==r) { Rotate(x[a].x,x[a].y,rad); return ; } push_down(a); int mid=(l+r)>>1; if(mid<a1) update(mid+1,r,a1,w,a<<1|1); else { update(l,mid,a1,w,a<<1); Rotate(x[a<<1|1].x,x[a<<1|1].y,rad); re[a<<1|1]+=w; } push_up(a); } int main() { int n,m,ca=1; while(scanf("%d%d",&n,&m)!=EOF) { if(ca!=1) printf("\n"); ca++; for(int i=1;i<=n;i++) { scanf("%d",&z[i]); z[i]=z[i-1]+z[i]; } memset(deg,0,sizeof(deg)); Build(1,n,1); for(int i=1;i<=m;i++) { int s,a; scanf("%d%d",&s,&a); s++; a=a-180; int delta=a-deg[s]; deg[s]=a; update(1,n,s,delta,1); printf("%.2lf %.2lf\n",x[1].x,x[1].y); } } return 0; }
线段树 poj 2991
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。