給定平面上大小為$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 |