poj2991 Crane 线段树
poj2991
学习的题解
在挑战程序设计竞赛（大白）上想弄懂树状数组，然后发现它先讲线段树，于是就先学线段树，于是就这道题卡了两个晚上。
首先是线段树的结构，一看书大致想起来一点。这里写的时候，就是一点，数组要开得够大，4倍的数据量才够。
这道题以线段树为载体，还承载了一个向量旋转的重要方法。一开始直接看题解、大白的式子一脸懵逼，然后看了题解上知道了它的rad值的含义以后，画个图，就能用两角差展开式推导出来，(x,y)的向量顺时针旋转α角度后得到的新坐标(x0,y0)可以用x,y,α表示。
极其难受的是，第二个晚上调试过程中 ，一直和题解一行行对照，最后猛然发现把update函数命名覆盖以后就可以跑出结果，然后锁定是double rad误申明成int rad的原因。很好，以后查低级bug又多了一个数据类型匹配的审查点。
上代码。其实已经改得和题解几乎一样了。但是有自己的一些注释，是不一样的可以起提醒作用的东西。
#include
#include
#include
#include
#define lson l,mid,rt<<1
#define rson mid,r,rt<<1|1
#define mx 10010using namespace std;
struct ST
{double x,y,lazy;
} T[mx<<2];//开得大一些 直接乘4
const double PI=asin(1.0)*2;
void build(int l,int r,int rt)
{T[rt].x=T[rt].lazy=0.0;if(r-l==1){scanf("%lf",&T[rt].y);return ;}int mid=(l+r)>>1;build(lson);build(rson);T[rt].y=T[rt<<1].y+T[rt<<1|1].y;
}
double pre[mx];
void update(int L,int R,double rad,int l,int r,int rt)//rad的类型设错一度让我崩溃
{double x,y;if(L==l && R==r){x=T[rt].x*cos(rad) + T[rt].y*sin(rad);y=T[rt].y*cos(rad) - T[rt].x*sin(rad);T[rt].x=x;T[rt].y=y;//把这部分整体旋转过来T[rt].lazy+=rad;//记得lazy值是相加的return ;}int mid=(l+r)>>1;if(T[rt].lazy)//让这个区间的左右孩子分别旋转{x=T[rt<<1].x*cos(T[rt].lazy) + T[rt<<1].y*sin(T[rt].lazy);y=T[rt<<1].y*cos(T[rt].lazy) - T[rt<<1].x*sin(T[rt].lazy);T[rt<<1].x=x,T[rt<<1].y=y;T[rt<<1].lazy+=T[rt].lazy;x=T[rt<<1|1].x*cos(T[rt].lazy) + T[rt<<1|1].y*sin(T[rt].lazy);y=T[rt<<1|1].y*cos(T[rt].lazy) - T[rt<<1|1].x*sin(T[rt].lazy);T[rt<<1|1].x=x,T[rt<<1|1].y=y;T[rt<<1|1].lazy+=T[rt].lazy;//要记得把lazy值下放T[rt].lazy=0.;}if(L>=mid) update(L,R,rad,rson);else if(R<=mid) update(L,R,rad,lson);else{update(L,mid,rad,lson);update(mid,R,rad,rson);}T[rt].x=T[rt<<1].x+T[rt<<1|1].x;T[rt].y=T[rt<<1].y+T[rt<<1|1].y;
}
int main()
{int n,c;while(~scanf("%d%d",&n,&c)){build(0,n,1);for(int i=1; i<=n; i++)pre[i]=PI;while(c--){int s,a;scanf("%d%d",&s,&a);double rad=a/180. * PI;update(s,n,pre[s]-rad,0,n,1);pre[s]=rad;printf("%.2lf %.2lf\n",T[1].x,T[1].y);}cout< 另外吐槽一句poj是真的难受，万能头文件不能用，asin(1.)都过不了，非得写成asin(1.0)，当时情况就是懵逼树上懵逼果，懵逼树下poj和我。
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！