P8000 [WFOI - 01] Cycle (circle)

Simplified statement: [$\texttt{Link}$](https://www.luogu.com.cn/paste/v7gqdh44)。 Setter’s note: これは非常に嫌な質問なので、あまり時間をかけたくない場合は、この質問を見る前に他の質問を終えることをお勧めします。

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$.

The first line contains a positive integer $n$. The next $n$ lines each contain $2$ integers, representing a point.

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$.

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.** Subtask ID | Constraints and Notes :-: | :-: **Subtask #0($\text{20 pts}$)** | $1\le n\le10$; $-10\le x_i,y_i \le 10$ **Subtask #1($\text{20 pts}$)** | $1\le n\le10^3$ **Subtask #2($\text{30 pts}$)** | $z>1$ **Subtask #3($\text{30 pts}$)** | No special restrictions. 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