← 返回题目列表

AtCoder · code_festival_china_c

C. 正多边形

中文机器翻译题面 查看原题

问题

你被给予 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

给定点在一条直线上。你不能用它们制作任何正多边形。