[poj 2991]Crane[线段树表示向量之和,而非数量]

题意:

起重机的机械臂, 由n段组成, 对某一些连接点进行旋转, 询问每次操作后的末端坐标.

思路:

由于旋转会影响到该点之后所有线段的角度, 因此容易想到用线段树记录角度, 成段更新. (但是不是每一次操作都要询问一次么? 那么懒惰标记还有用么? 如果使用懒惰标记, 将一些线段视为整体, 那么这些线段岂不是又要用一个线段树记录一段区间的总长? 树状数组亦可...)

将向量视为数量整体加和, 融入到线段树的操作中, 就可以避免角度和坐标分离的麻烦事..

旋转角度与坐标的关系:

根据位移向量绕原点旋转的表达式, 借助三角函数公式, 可推得矩阵形式的向量旋转公式.

[ x1 ] = [ cos a sin a ] [ x0 ]

[ y1 ] [ -sin a cos a] [ y0 ]

思维上的不足:

对线段树的求和理念理解不深, 只是想到了角度的加和, 殊不知向量本身也可以加和, 而且"和向量"与"分向量"的关系是层层细分下去的.

有了这样的思维框架, 就不难照顾好 sx, sy, sd 这三个数组了. 因为要表示一个"位移向量", 使用这三个参数是自然的.

#include<cstdio>

#include<cmath>

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

///把所有的区间看做等效的一条线段

///旋转的时候认为是只旋转宏观的!中间的细节是不考虑的

using namespace std;

const int mm=11111;

int sd[mm<<2],degree[mm];

double sx[mm<<2],sy[mm<<2];

void rotate(int rt,int sd)

{

    double d=sd*asin(1.0)/90.0;//degrees in rad

    double x=cos(d)*sx[rt]-sin(d)*sy[rt];

    double y=sin(d)*sx[rt]+cos(d)*sy[rt];

    sx[rt]=x,sy[rt]=y;// rotate the sub-tree as a whole~!

}

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 pushup(int rt)

{

    sx[rt]=sx[rt<<1]+sx[rt<<1|1];

    sy[rt]=sy[rt<<1]+sy[rt<<1|1];

}

void build(int l,int r,int rt)

{

    sd[rt]=0;//segment delta degree (must as a whole)

    if(l==r)

    {

        scanf("%lf",&sy[rt]);

        sx[rt]=0;//segment coordinates

        return;

    }

    int m=(l+r)>>1;

    build(lson);

    build(rson);

    pushup(rt);//only coordinates

}

void updata(int p,int d,int l,int r,int rt)

{

    if(p<l)//if this sub-tree is completely in the rorated range, rotate.

    {

        rotate(rt,d);

        sd[rt]+=d;

        return;

    }

    if(sd[rt])pushdown(rt);//修正儿子的delta degree

    int m=(l+r)>>1;

    if(p<m)updata(p,d,lson);//如果[涉及]左儿子,就更新

    updata(p,d,rson);///[一定][涉及]右儿子!

    pushup(rt);///再更新总体的坐标

}

int main()

{

    int i,j,n,m,flag=0;

    while(~scanf("%d%d",&n,&m))

    {

        if(flag)puts("");else flag=1;//判断第一个

        build(1,n,1);

        for(i=0;i<n;++i)degree[i]=180;//degree after ith segment

        while(m--)

        {

            scanf("%d%d",&i,&j);

            updata(i,j-degree[i],1,n,1);//(index, delta degree, tree)

            degree[i]=j;

            printf("%.2lf %.2lf\n",fabs(sx[1])<1e-8?0:sx[1],fabs(sy[1])<1e-8?0:sy[1]);

        }//output root's coordinates, caution: precision

    }

    return 0;

}

巴特西

[poj 2991]Crane[线段树表示向量之和,而非数量]

最新文章

热门文章