2071 . 分點問題（二）
TopCoder
Tags
Description
給定平面上大小為$N$的點集$P$，保證$N$為偶數且$P$中任意三點皆不共線。
定義$C(S)$為點集$S$的凸包的頂點數量。請求出一種將$P$分成兩個集合不相交$X, Y$的方法（即$X \cap Y = \emptyset$，$X \cup Y = P$），使得$C(X) = C(Y)$，或者判斷不存在滿足條件的解。
Input Format
輸入第一行為$N$，代表點集$P$的大小為$N$。
接著$N$行每行有2個整數$x_i, y_i$，代表第$i$個點的座標。
對於所有的測資，$N \leq 4\times 10^ 5, |x_i|, |y_i| \leq 10^ 9$。
Output Format
若不可能將$P$分成兩個集合$X, Y$滿足題目要求，輸出一行No。
否則，請在第一行輸出Yes。
接著輸出一行代表點集$X$的大小$|X|$，再下一行輸出$|X|$個正整數代表$X$中的點的編號。
接著輸出一行代表點集$Y$的大小$|Y|$，再下一行輸出$|Y|$個正整數代表$Y$中的點的編號。
（同一行的數字皆以空白隔開。）
若有多組可能的解，輸岀任意一組解即可。
Sample Input 1
6
0 0
1 0
0 1
2 2
3 2
2 3
0 0
1 0
0 1
2 2
3 2
2 3
Sample Output 1
Yes
3
1 2 3
3
4 5 6
3
1 2 3
3
4 5 6
Hints
Problem Source
Problem set by Tau
建國中學107學年度校隊選拔：複試pD
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~9 | $N \leq 20$ | 17 |
| 2 | 0~14 | $N \leq 2000$ | 32 |
| 3 | 0~19 | $N \leq 20000$ | 21 |
| 4 | 0~23 | 無額外限制 | 30 |