站点公告
用户登陆
站点日历
<<  < 2013 - 8 >  >>
日 一 二 三 四 五 六
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
我的相册
最新日志
最新评论
日志搜索
最新留言
我的好友
我的圈子
友情链接
站点统计




[ 2013-8-13 13:47:00 | By: acm_letgo ]
今天做一个线段树题有感
今天做了一个线段树的题，虽然调试了好久才调试出来，但是还是觉得挺有收货的。
题目的编号是：POJ2991

先上题目描述吧！

Description

ACM has bought a new crane (crane -- je?áb) . The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 ≤ i < n. The beginning of the first segment is fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen. 

Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180o. The operator issues commands that change the angle in exactly one joint. 

Input

The input consists of several instances, separated by single empty lines. 

The first line of each instance consists of two integers 1 ≤ n ≤10 000 and c 0 separated by a single space -- the number of segments of the crane and the number of commands. The second line consists of n integers l1,..., ln (1 li 100) separated by single spaces. The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 ≤ s < n, 0 ≤ a ≤ 359) separated by a single space -- the order to change the angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).

Output

The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space -- the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point. 

The outputs for each two consecutive instances must be separated by a single empty line.

Sample Input

2 1
10 5
1 90

3 2
5 5 5
1 270
2 90

Sample Output

5.00 10.00

-10.00 5.00
-5.00 10.00


题目的大意是说给你n跟杆，邻接的杆用铰接的方式连接（可以在同一平面内转动）
开始的时候所有的杆从（0,0）开始在y轴上连接成一根直线。
下面有许多操作，每个操作位si，ai，即把ai和ai+1之间的夹角变为si度（是变为不是增加，晕死，老子就是因为这里贡献了若干次wa）
看完题目以后相信学过线段树的人大概就知道了，这是一个线段树的题目。每次改变一下夹角，就是把后面所有的杆的方向都改变了，如果把每个杆看成一个向量，就相当于这个向量旋转了一样。
所以这里还要用到一点点的计算几何的知识呢。
一个向量(x,y)逆时针旋转a度后，该向量变为：(x*cosa-y*sina,x*sina+y*cosa)（我的代码里写的是顺时针旋转，一样的，只要把a变为-a就可以了）
到这里，题目的解题脉络就基本上已经浮出水面了。

下面上代码吧！

＃i nclude <iostream>
＃i nclude <cmath>
＃i nclude <cstdio>
#define maxn 10110
#define Cur int rt,int l,int r
#define Now int L,int R,int v
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define getmid int mid=(l+r)>>1
#define PI 3.14159265358979323846
#define exp 1e-9
using namespace std;

double x[4*maxn],y[4*maxn],Si[360],Co[360];
int deg[4*maxn],L[maxn],n,m,angle[maxn];

void build(Cur)
{
    deg[rt]=0;
    x[rt]=0;
    if (l==r)
    {
        y[rt]=L[l];
        return;
    }
    getmid;
    build(lson);
    build(rson);
    y[rt]=y[rt<<1]+y[rt<<1|1];
}

void rot(int rt,int degree)
{
    double tepx=x[rt],tepy=y[rt];
    x[rt]=tepx*Co[degree]+tepy*Si[degree];
    y[rt]=tepy*Co[degree]-tepx*Si[degree];
}

void PushDown(int rt)
{
    if (deg[rt]==0) return;
    rot(rt<<1,deg[rt]);
    rot(rt<<1|1,deg[rt]);
    deg[rt<<1]=deg[rt<<1]+deg[rt];
    deg[rt<<1|1]=deg[rt<<1|1]+deg[rt];
    while (deg[rt<<1]>=360) deg[rt<<1]-=360;
    while (deg[rt<<1|1]>=360) deg[rt<<1|1]-=360;
    deg[rt]=0;
}

void ***(Cur,Now)
{
    if (L<=l && R>=r)
    {
        rot(rt,v);
        deg[rt]=(deg[rt]+v);
        while (deg[rt]>=360) deg[rt]-=360;
        return;
    }
    PushDown(rt);
    getmid;
    if (L<=mid) ***(lson,L,R,v);
    if (R> mid) ***(rson,L,R,v);
    x[rt]=x[rt<<1]+x[rt<<1|1];
    y[rt]=y[rt<<1]+y[rt<<1|1];
}

int main()
{
    int si,ai,cas=0,tmp;
    for (int i=0; i<=360; i++)
        Si[i]=sin((i/180.0)*PI),Co[i]=cos((i/180.0)*PI);
    while (scanf("%d%d",&n,&m)==2)
    {
        for (int i=1; i<n; i++) angle[i]=180;
        if (cas++) printf("\n");
        for (int i=1; i<=n; i++) scanf("%d",&L[i]);
        build(1,1,n);
        while (m--)
        {
            scanf("%d%d",&si,&ai);
            tmp=angle[si]-ai;
            while (tmp<0) tmp+=360;
            while (tmp>=360) tmp-=360;
            ***(1,1,n,si+1,n,tmp);
            printf("%.2lf %.2lf\n",x[1]+exp,y[1]+exp);
            angle[si]=ai;
        }
    }
    return 0;
}

代码风格略挫
924 KB641 ms


跑出来的是这个效果，嘻嘻，还行，感觉这个题目做完还是有收获的呢。
发表评论：
天涯博客欢迎您！