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$。
| 子任務（測資） | 額外限制 | 分數 |
| 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 |
Output Format
若不可能將$P$分成兩個集合$X, Y$滿足題目要求，輸出一行No。
否則，請在第一行輸出Yes。
接著輸出一行代表點集$X$的大小$|X|$，再下一行輸出$|X|$個正整數代表$X$中的點的編號。
接著輸出一行代表點集$Y$的大小$|Y|$，再下一行輸出$|Y|$個正整數代表$Y$中的點的編號。
（同一行的數字皆以空白隔開。）
若有多組可能的解，輸岀任意一組解即可。
Sample Input
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
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
For Testdata: 0 ~ 9, Score: 17
For Testdata: 0 ~ 14, Score: 32
For Testdata: 0 ~ 19, Score: 21
For Testdata: 0 ~ 23, Score: 30
For Testdata: 0 ~ 14, Score: 32
For Testdata: 0 ~ 19, Score: 21
For Testdata: 0 ~ 23, Score: 30
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) |
|---|---|---|---|
| 0 | 1000 | 131072 | 262144 |
| 1 | 1000 | 131072 | 262144 |
| 2 | 1000 | 131072 | 262144 |
| 3 | 1000 | 131072 | 262144 |
| 4 | 1000 | 131072 | 262144 |
| 5 | 1000 | 131072 | 262144 |
| 6 | 1000 | 131072 | 262144 |
| 7 | 1000 | 131072 | 262144 |
| 8 | 1000 | 131072 | 262144 |
| 9 | 1000 | 131072 | 262144 |
| 10 | 1000 | 131072 | 262144 |
| 11 | 1000 | 131072 | 262144 |
| 12 | 1000 | 131072 | 262144 |
| 13 | 1000 | 131072 | 262144 |
| 14 | 1000 | 131072 | 262144 |
| 15 | 1000 | 131072 | 262144 |
| 16 | 1000 | 131072 | 262144 |
| 17 | 1000 | 131072 | 262144 |
| 18 | 1000 | 131072 | 262144 |
| 19 | 1000 | 131072 | 262144 |
| 20 | 1000 | 131072 | 262144 |
| 21 | 1000 | 131072 | 262144 |
| 22 | 1000 | 131072 | 262144 |
| 23 | 1000 | 131072 | 262144 |