2071 . 分點問題（二）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb a
我就爛

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

9.0% (6/67)

Tags

CKcon 2018-CKcon-fin

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

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

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 (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
Submit
Status
Ranklist
Back to Top