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的方法(即XY=XY=P),使得C(X)=C(Y),或者判斷不存在滿足條件的解。

Input Format

輸入第一行為N,代表點集P的大小為N
接著N行每行有2個整數xi,yi,代表第i個點的座標。

對於所有的測資,N4×105,|xi|,|yi|109

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 N20 17
2 0~14 N2000 32
3 0~19 N20000 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