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

Sample Output

Yes
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

No.	Time Limit (ms)	Memory Limit (KiB)
0	1000	131072
1	1000	131072
2	1000	131072
3	1000	131072
4	1000	131072
5	1000	131072
6	1000	131072
7	1000	131072
8	1000	131072
9	1000	131072
10	1000	131072
11	1000	131072
12	1000	131072
13	1000	131072
14	1000	131072
15	1000	131072
16	1000	131072
17	1000	131072
18	1000	131072
19	1000	131072
20	1000	131072
21	1000	131072
22	1000	131072
23	1000	131072

2071 . 分點問題（二）

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags