Background

Simplified statement: $\texttt{Link}$。

Setter’s note: これは非常に嫌な質問なので、あまり時間をかけたくない場合は、この質問を見る前に他の質問を終えることをお勧めします。

Problem Description

You are given a set of points $a$ on the coordinate plane. You need to find a subset of points $b$ and a vector $x$ such that $\exist\ z\in N^+,\{b\cup b+x\cup b+2x\cup\dots\cup b+zx=a\}$.

Now you are asked to find any triple $b_0,x_0,z_0$, where $z_0$ is the maximum $z$ among all triples satisfying the condition, any three points in $b_0$ are not collinear, any four points do not form a trapezoid or a parallelogram, and $b_0\cap b_0+x_0=\varnothing,b_0\cap b_0+2x_0=\varnothing,\dots,b_0\cap b+yx_0=\varnothing|{y\to+\infty}$.

Here, $b+x$ means the set of points obtained by translating every point in $b$ by the vector $x$.

Input Format

The first line contains a positive integer $n$.

The next $n$ lines each contain $2$ integers, representing a point.

Output Format

Output a total of $4$ lines:

The first line contains an integer $|b|$.

The second line contains $|b|$ integers $b_1,b_2,\dots,b_{|b|}$ (corresponding indices).

The third line contains two integers $x$.

The fourth line contains an integer $z$.

4
0 0
0 1
1 0
1 1

2
1 3
0 1
1

3
0 0
0 1
1 0

3
1 2 3
0 0
0

Hint

Since the sample explanation would only repeat the statement, and it is believed that if you have reached this problem you should be able to understand its meaning, no sample explanation is provided (actually the setter is lazy).

This problem uses bundled Subtask tests.

For $100\%$ of the testdata, $1\le n\le10^5$, the coordinate range of points is $\in\left(-10^9,10^9\right)$, and the testdata guarantees that a solution exists.

Translated by ChatGPT 5