TopCoder

User's AC Ratio

0.0% (0/3)

Submission's AC Ratio

0.0% (0/21)

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