#P18159. Alternating Cycle
Alternating Cycle
Alternating Cycle
平面上有 个点,任意三点不共线。你可以选出一个非空子集并为它指定一个顺序。若选出的有序点列为 ,要求对 ,角 随着 增大依次交替为顺时针和逆时针(下标模 )。注意 必须为偶数,否则由奇偶性可知不可能。这样的有序子集称为交错环。
求点数最少的交错环并输出,或报告不存在。
环的边允许相交;只要求所选点互不相同,并满足每个顶点处的循环转向交替。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 (),表示一个点。保证点互不相同且任意三点不共线。
输出格式
若不存在交错环,输出 -1。
否则先输出 ,再输出 行,每行两个整数,表示交错环上的点(顺序即为环的顺序)。这些点必须是输入点的子集。
样例 1
输入:
6
10 15
20 15
15 23
0 31
15 0
30 30
输出:
6
0 31
10 15
15 0
20 15
30 30
15 23
样例 2
输入:
4
0 0
0 1
1 0
1 1
输出:
-1