poj-2991 Crane 個人感想和做法

原題位址：http://poj.org/problem?id=2991

題意：二維平面上的線段，給出每條線段的長度，他們連成一條線，一開始豎直向上，給出某一段與下一段的角度（逆時針），輸出最後的坐标的位置

分析：由于題目有多次查詢，每次查詢都需要對一個區間更改并且輸出一個值，很容易聯想到線段樹。然鵝問題來了，如何用線段樹去解題（老實說我線段樹剛入門看到這題一臉懵逼）。假如每次修改兩段之間的夾角，然後一步一步計算坐标，直到最後，那麼最壞情況下從1開始遞推到n，複雜度是O（n），不是線段樹。

進行區間修改的時候，我們需要找到一樣東西是被各線段通用的，假如按照上文的方法，每個線段都有其對應的點，都不一樣，就沒辦法區間修改。假如将各線段看成向量，向量繞點旋轉（如圖，a 與 b向量繞a下面那個點旋轉k角度，可以看到 b也轉了一樣的度數）

是以似乎就找到了一個共通的值可以區間修改，然後下面的問題是如何求得最末尾的點。

我們讓線段樹（l，r）表示從l指向r的向量，因為原點總是（0，0），是以可以通過正交分解向量，橫縱坐标分别相加得到，可以看到線段樹（0，n）所代表的值就是答案。

總體思路：

使用線段樹維護區間向量（注意線段樹的葉子代表向量（0，1），（1，2）……），使用一個ang數組記錄每個區間向量的角度。更新的時候不斷二分，假如更新的點在區間的l左邊，那麼隻需要整個區間的那一條從l指向r的向量旋轉并且記錄（用ang記錄），假如更新的點在l和r中間那麼就繼續二分。

下面是首先需要知道的小知識：（其實是我不知道）

求一個向量（x0,y0）逆時針旋轉B度：

x1= x0 * cosB - y0 * sinB                  y1 = x0 * sinB + y0 * cosB

順時針：

x1= x0 * cosB + y0 * sinB                  y1 = -x0 * sinB + y0 * cosB 

注意：cos sin csin ccos 傳入的都是弧度制，并不是角度

角度轉弧度：

弧度=角度*Pi/180

主體函數分析：

void update(int l,int r,int aim,int index,double angle){
	if(aim<=l||aim>=r) return ; 
	else{  //這個就是區間更新的判定條件 
		int mid=(l+r)>>1;
		update(l,mid,aim,index<<1,angle);
		update(mid,r,aim,index<<1|1,angle);
		if(aim<=mid){ //記錄右邊子樹，整課旋轉 
			ang[index]+=angle; // 記錄，友善往下推 
		} 
		double ssin=sin(ang[index]),ccos=cos(ang[index]); //更新！ 
		tree[index].x=tree[index<<1].x+(ccos*tree[index<<1|1].x-ssin*tree[index<<1|1].y); 
		tree[index].y=tree[index<<1].y+(ssin*tree[index<<1|1].x+ccos*tree[index<<1|1].y);
	}
} 
           

需要對目标點（aim）右邊的所有線段操作，是以在遇到 l<aim<r 的時候，假如aim在mid左邊，則右邊需要全部更新，是以在本層打上記号并且最後運算時将本層的角度值與右兒子結合運算，而左兒子由于不是全部都在aim右邊，是以需要對其繼續二分，在下一層把值算好之後傳回上一層直接參與計算（不與本層角度值一起運算）。

AC代碼：

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=10002;
int dis[maxn]; //dis 為各段距離 
double ang[maxn*4],n_ang[maxn]; // ang: 各段角度  n_ang： 隻是小段的角度 
int n,q;
struct node{
	double x,y;
}tree[maxn*4];
void build_tree(int l,int r,int index){ //正常建樹 
	ang[index]=0; //180°初始化為弧度即弧度為0 
	if(r-l==1){  //線段樹的葉子是 0 1  1 2   2 3  3 4 
		tree[index].x=0;
		tree[index].y=dis[l];
		return;
	}
	int mid=(l+r)>>1;
	build_tree(l,mid,index<<1);
	build_tree(mid,r,index<<1|1); //這裡得是mid 不是 mid+1 
	tree[index].y=tree[index<<1].y+tree[index<<1|1].y;
	tree[index].x=0; 
}
void update(int l,int r,int aim,int index,double angle){
	if(aim<=l||aim>=r) return ; 
	else{  //這個就是區間更新的判定條件 
		int mid=(l+r)>>1;
		update(l,mid,aim,index<<1,angle);
		update(mid,r,aim,index<<1|1,angle);
		if(aim<=mid){ //記錄右邊子樹，整課旋轉 
			ang[index]+=angle; // 記錄，友善往下推 
		} 
		double ssin=sin(ang[index]),ccos=cos(ang[index]); //更新！ 
		tree[index].x=tree[index<<1].x+(ccos*tree[index<<1|1].x-ssin*tree[index<<1|1].y); 
		tree[index].y=tree[index<<1].y+(ssin*tree[index<<1|1].x+ccos*tree[index<<1|1].y);
	}
} 
void solve(){
	fill(n_ang+1,n_ang+n+1,acos(-1.0)); 
	while(q--){
		int num,angle; scanf("%d %d",&num,&angle);
		double a=angle/360.0*2*acos(-1.0); //角度變弧度 
		update(0,n,num,1,a-n_ang[num]);
		n_ang[num]=a;
		printf("%.2f %.2f\n",tree[1].x,tree[1].y);
	}
}
int main(){
	while(cin>>n>>q){
		for(int i=0;i<n;i++) scanf("%d",&dis[i]);
		build_tree(0,n,1); //從0開始 
		solve(); 
	}
	return 0;
} 
/*
2 1
10 5
1 90

3 2
5 5 5
1 270
2 90
*/