TopCoder

中數理論

「因為時間與空間獨立，這些時空的聯合分布可以透過貝氏定理，找出先後的條件機率，並透過微積分找出體用的相對機率，即 PDF/PMF 或 CDF。」

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

9.0% (6/67)

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

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

2071 . 分點問題（二）