給定平面上大小為$N$的點集$P$,保證$N$為偶數且$P$中任意三點皆不共線。
定義$C(S)$為點集$S$的凸包的頂點數量。請求出一種將$P$分成兩個集合不相交$X, Y$的方法(即$X \cap Y = \emptyset$,$X \cup Y = P$),使得$C(X) = C(Y)$,或者判斷不存在滿足條件的解。
輸入第一行為$N$,代表點集$P$的大小為$N$。
接著$N$行每行有2個整數$x_i, y_i$,代表第$i$個點的座標。
對於所有的測資,$N \leq 4\times 10^ 5, |x_i|, |y_i| \leq 10^ 9$。
若不可能將$P$分成兩個集合$X, Y$滿足題目要求,輸出一行No
。
否則,請在第一行輸出Yes
。
接著輸出一行代表點集$X$的大小$|X|$,再下一行輸出$|X|$個正整數代表$X$中的點的編號。
接著輸出一行代表點集$Y$的大小$|Y|$,再下一行輸出$|Y|$個正整數代表$Y$中的點的編號。
(同一行的數字皆以空白隔開。)
若有多組可能的解,輸岀任意一組解即可。
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 131072 | 262144 | |
1 | 1000 | 131072 | 262144 | |
2 | 1000 | 131072 | 262144 | |
3 | 1000 | 131072 | 262144 | |
4 | 1000 | 131072 | 262144 | |
5 | 1000 | 131072 | 262144 | |
6 | 1000 | 131072 | 262144 | |
7 | 1000 | 131072 | 262144 | |
8 | 1000 | 131072 | 262144 | |
9 | 1000 | 131072 | 262144 | |
10 | 1000 | 131072 | 262144 | |
11 | 1000 | 131072 | 262144 | |
12 | 1000 | 131072 | 262144 | |
13 | 1000 | 131072 | 262144 | |
14 | 1000 | 131072 | 262144 | |
15 | 1000 | 131072 | 262144 | |
16 | 1000 | 131072 | 262144 | |
17 | 1000 | 131072 | 262144 | |
18 | 1000 | 131072 | 262144 | |
19 | 1000 | 131072 | 262144 | |
20 | 1000 | 131072 | 262144 | |
21 | 1000 | 131072 | 262144 | |
22 | 1000 | 131072 | 262144 | |
23 | 1000 | 131072 | 262144 |