← 返回题目列表

Codeforces · 850/A

A. 五维点

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

给定 5 维空间中的 n 个点集。这些点被标记为从 1 到 n。没有两点重合。

如果给定集合中存在不同的点 b 和 c(不等于 a),使得向量 $${ \vec { a } } { \vec { b } }$$ 和 $${ \vec { a } } { \vec { c } }$$ 之间的角度为锐角(即严格小于 $$90^\circ$$),我们将称点 a 为坏点。否则,该点称为好点。

5 维空间中向量 $$\overrightarrow{\tau}$$ 和 $${ \overrightarrow { y } }$$ 之间的角度定义为 $$\arccos\left(\frac{\vec{x} \cdot \vec{y}}{|\vec{x}||\vec{y}|}\right)$$,其中 $$\vec{x} \cdot \vec{y} = x_{1} y_{1} + x_{2} y_{2} + x_{3} y_{3} + x_{4} y_{4} + x_{5} y_{5}$$ 是标量积,$$|\vec{x}| = \sqrt{\vec{x} \cdot \vec{x}}$$ 是 $$\overrightarrow{\tau}$$ 的长度。

给定点列表,按升序打印好点的索引。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 103) — 点数。

接下来的 n 行输入包含五个整数 ai、bi、ci、di、ei (|ai|, |bi|, |ci|, |di|, |ei| ≤ 103) — 第 i 个点的坐标。所有点都是不同的。

输出

首先,打印一个整数 k — 好点的数量。

然后,打印 k 个整数,每个整数占一行——按升序排列的好点的索引。

示例

输入 #1

6
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

输出 #1

1
1

输入 #2

3
0 0 1 2 0
0 0 9 2 0
0 0 5 9 0

输出 #2

0

注意

在第一个示例中,第一个点与所有其他点对形成 $$90^\circ$$ 角度,因此效果很好。

在第二个示例中,沿着 cd 平面,我们可以看到点如下所示:

我们可以看到这里所有的角都是锐角,所以没有点是好的。