poj 2991 Crane(ベクトル回転+セグメントツリーセグメント更新)
Crane
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 1609
Accepted: 416
Special Judge
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., 180
o. 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
CTU Open 2005
タイトル:http://poj.org/problem?id=2991
题意:あなたに1つのn节の构成のクレーンをあげて、各2节は直接回転することができて、最初は各节はすべてy轴の上で、今毎回iとi+1の角度を回転することに対して、末端の座標を求めます.
解析:セグメントツリーを計算ジオメトリに適用する興味深い問題です.まず、計算ジオメトリの知識が必要です.
1.ベクトル(x,y)では、ベクトルが反時計回りにaラジアンを回転した後のベクトルは(cos a*x-sina*y,sina*x+cos a*y)
2.ベクトルの和はちょうどこれらのベクトルの頭と尾がつながっているところを指しています.つまり、各セグメントをベクトルと見なしています.では、このベクトルの和は末端の座標を指しています.
3.回転第iとi+1の角度は、i+1およびその上のすべてのベクトルが同じ角度で回転する
上記の知識によって、テーマを線分樹に変換して解決することができ、線分樹を構築し、ベクトル回転の角度を保存し、ベクトル座標の和、角度は積算され、iを回転するたびに、線分樹の中のi+1からnのすべての角度に回転の角度を加え、もちろん遅延マークを使いますが、新しい回転角度が来るたびに、この区間を直接回転します.そしてさらに角度を遅延マークに加算して、順番が逆になるとエラーになり、最初はこのように書くとwaになります...下に更新する場合も同じですが、回転してから遅延フラグを更新し、具体的にはコードを見ましょう..精度の問題も気持ち悪くて、-0.00を出力して、毎回回転しました==
コード:
Time Limit: 2000MS
Memory Limit: 65536K
Total Submissions: 1609
Accepted: 416
Special Judge
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., 180
o. 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 905.00 10.00
-10.00 5.00
-5.00 10.00CTU Open 2005
タイトル:http://poj.org/problem?id=2991
题意:あなたに1つのn节の构成のクレーンをあげて、各2节は直接回転することができて、最初は各节はすべてy轴の上で、今毎回iとi+1の角度を回転することに対して、末端の座標を求めます.
解析:セグメントツリーを計算ジオメトリに適用する興味深い問題です.まず、計算ジオメトリの知識が必要です.
1.ベクトル(x,y)では、ベクトルが反時計回りにaラジアンを回転した後のベクトルは(cos a*x-sina*y,sina*x+cos a*y)
2.ベクトルの和はちょうどこれらのベクトルの頭と尾がつながっているところを指しています.つまり、各セグメントをベクトルと見なしています.では、このベクトルの和は末端の座標を指しています.
3.回転第iとi+1の角度は、i+1およびその上のすべてのベクトルが同じ角度で回転する
上記の知識によって、テーマを線分樹に変換して解決することができ、線分樹を構築し、ベクトル回転の角度を保存し、ベクトル座標の和、角度は積算され、iを回転するたびに、線分樹の中のi+1からnのすべての角度に回転の角度を加え、もちろん遅延マークを使いますが、新しい回転角度が来るたびに、この区間を直接回転します.そしてさらに角度を遅延マークに加算して、順番が逆になるとエラーになり、最初はこのように書くとwaになります...下に更新する場合も同じですが、回転してから遅延フラグを更新し、具体的にはコードを見ましょう..精度の問題も気持ち悪くて、-0.00を出力して、毎回回転しました==
コード:
#include<cstdio>
#include<iostream>
#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;
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;
}
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;
if(l==r)
{
scanf("%lf",&sy[rt]);
sx[rt]=0;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void updata(int p,int d,int l,int r,int rt)
{
if(p<l)
{
rotate(rt,d);
sd[rt]+=d;
return;
}
if(sd[rt])pushdown(rt);
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;
while(m--)
{
scanf("%d%d",&i,&j);
updata(i,j-degree[i],1,n,1);
degree[i]=j;
printf("%.2lf %.2lf
",fabs(sx[1])<1e-8?0:sx[1],fabs(sy[1])<1e-8?0:sy[1]);
}
}
return 0;
}