#P18159. Alternating Cycle

Alternating Cycle

Alternating Cycle

平面上有 nn 个点,任意三点不共线。你可以选出一个非空子集并为它指定一个顺序。若选出的有序点列为 p0,p1,…,pk−1p_0,p_1,\dots,p_{k-1},要求对 1≤i≤k+11\le i\le k+1,角 ∠pi−1pipi+1\angle p_{i-1}p_ip_{i+1} 随着 ii 增大依次交替为顺时针和逆时针(下标模 kk)。注意 kk 必须为偶数,否则由奇偶性可知不可能。这样的有序子集称为交错环。

求点数最少的交错环并输出,或报告不存在。

环的边允许相交;只要求所选点互不相同,并满足每个顶点处的循环转向交替。

输入格式

第一行一个整数 nn(1≤n≤2⋅1051\le n\le 2\cdot10^5)。

接下来 nn 行,每行两个整数 x,yx,y(0≤x,y≤1090\le x,y\le 10^9),表示一个点。保证点互不相同且任意三点不共线。

输出格式

若不存在交错环,输出 -1。

否则先输出 kk,再输出 kk 行,每行两个整数,表示交错环上的点(顺序即为环的顺序)。这些点必须是输入点的子集。

样例 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