[WFOI - 01] 循环节(circle)

题目背景

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

题目描述

给你一个坐标系上的点集 $a$,你需要找出一个子点集 $b$ 和一个向量 $x$,使得 $\exist\ z\in N^+,\{b\cup b+x\cup b+2x\cup\dots\cup b+zx=a\}$。 现在想让你求出任意一对 $b_0,x_0,z_0$,其中 $z_0$ 为所有满足条件的三元组中 $z$ 最大的,$b_0$ 中任意三点不共线,任意四点不构成梯形或平行四边形且 $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}$。 其中 $b+x$ 的意思是,$b$ 中的所有点都平移向量 $x$ 后组成的点集。

输入输出格式

输入格式


第一行一个正整数 $n$。 接下来 $n$ 行,每行 $2$ 个整数,表示一个点。

输出格式


输出共 $4$ 行: 第一行一个整数 $|b|$。 第二行 $|b|$ 个整数 $b_1,b_2,\dots,b_{|b|}$(对应编号)。 第三行两个整数 $x$。 第四行一个整数 $z$。

输入输出样例

输入样例 #1

4
0 0
0 1
1 0
1 1

输出样例 #1

2
1 3
0 1
1

输入样例 #2

3
0 0
0 1
1 0

输出样例 #2

3
1 2 3
0 0
0

说明

由于本题有样例解释也只是照着念一遍,并且相信既然您都做到这一题来了应该能读懂题目含义,所以本题不提供样例解释(~~其实是出题人懒~~)。 **本题采用 Subtask 捆绑测试。** Subtask 编号 | 数据规模与约定 :-: | :-: **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}$)** | 无特殊限制 对于 $100\%$ 的数据,$1\le n\le10^5$,点的坐标范围 $\in\left(-10^9,10^9\right)$,数据保证有解。