IOI '06 Joining Points

這題沒有Judge，所以自己寫了一個應該是可以AC的啦XD                                                                           .




很棒的題目。


Description:


Joining Points是一個獨人遊戲。

平面上有g個綠點  r個紅點   (2 <= g,r <= 50 000)

所有點都是整數座標   座標範圍是0~s (s <= 200 000 000)


保證(0,s)和(s,s)有綠點  (s,0)和(0,0)有紅點 並且任三點不共線

遊戲勝利的條件是  用g-1條線段把所有綠點連起來  用r-1條線段把所有紅點連起來

並且所有線段不交叉(共端點不算交叉)

保證一定有解  請輸出任意一種連線方案


Input

第一行: 整數g。接下來g行: 從綠點的編號1開始到g，每一行有二個以空白隔開的整數，
代表一個綠點的xi與yi 座標。第g+2行: 整數 r。接下來r行: 從紅點的編號1開始到r，
每一行有二個以空白隔開的整數，代表一個紅點的xi與yi 座標。

Output

共應輸出g-1+r-1行
每行包含兩個整數一個字元   前兩個整數代表這條線段所連接兩點編號
字元表示所連接兩點顏色


Sample Input
6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400


Sample Output
1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r



Solution:






這題目是很棒的D&C。時間複雜度：O(n lg n)


核心思想：

考慮一個三角形  v1 v2 v3 ，其中 v1,v2同色   v3異色

(1)如果中間沒有其他點    結束
(2)如果中間全部剩下的點同色    把那些點全部連到同一個頂點    結束
(3)其他：
選出一個跟v3同色的內部點vp，連v3-vp
然後對v1,v2,vp    v2,v3,vp   v3,v1,vp遞迴



很顯而易見遞迴三角形個數是和(g+r)同數量級，

如果對每個三角形O(g+r)檢查，就有了一個O((g+r)^2)算法   值55分


但是可以發現，其實對同一層    只需要合計O(g+r)的複雜度就可以
總共不會超過lg級別層，所以複雜度O(n lg n)ˇ



至於實做，我是以串列實做。










code(Judge程式，會告訴你是哪裡出錯)

http://codepad.org/rwc0RnZq

對了提一下，檢查是用Disjoint Set確定連通性，Sweep Line Algorithm檢查是否有交點




code(AC code)

http://codepad.org/q6v18QD5




testdata / solution (official)

http://olympiads.win.tue.nl/ioi/ioi2006/contest/day2/points/