TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

6.8% (5/74)

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

Sample Output 1

Yes
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

Testdata and Limits

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