问题
你被给予 N 直角坐标平面上的整数点阵, 您想从中选择一些点,通过用直线连接所选点来形成正多边形。另外,您希望选择尽可能多的点来形成正多边形。
确定应选择哪些点来构建具有最多可能顶点的正多边形。 如果有多个可能的答案,您可以选择其中之一。
输入
输入按以下格式给出。
N x_1 y_1 x_2 y_2 : x_N y_N
- 在第一行,您将得到一个整数 N (1 \leq N \leq 1,000),给定的整数格点数。
- 关于以下内容 N 行,您将获得每个格子的坐标。 的 i-th (1 \leq i \leq N) 行由两个整数组成 x_i,y_i (-10^9 \leq x_i,y_i \leq 10^9),x,y 坐标 分别为 i第格子。
- 每个给定的格子都保证是不同的。换句话说,对于任何 2 整数 i,j(1 \leq i,j \leq N),如果 i \neq j 然后 (x_i,y_i)≠(x_j,y_j) 成立。
输出
第一行,输出 m,您选择创建具有最多可能顶点的正多边形的点数。
关于以下内容 m 行,输出索引( 您选择的每个点的1-已索引) 按升序排列 .
如果你不能从给定的点创建任何正多边形,只需输出一条包含 0.
输入示例 1
6 1 0 -1 0 0 1 0 -1 1 2 -1 2
输出示例 1
4 1 2 3 4
其中给定 6 积分,您可以选择 4 点 (1,0),(-1,0),(0,1),(0,-1) 制作一个具有最多顶点的正正方形。所以答案是 4 以及这些点的索引。
的 4 点 (-1,0),(1,0),(1,2),(-1,2) 也可以制作正方体。所以,他们的指数, {1,2,5,6},也将被认为是正确的。
输入示例 2
4 0 0 1 0 2 0 3 0
输出示例 2
0
给定点在一条直线上。你不能用它们制作任何正多边形。