English · Original
Chinese · Translation
Formal · Original
You are given set of _n_ points in 5-dimensional space. The points are labeled from 1 to _n_. No two points coincide.
We will call point _a_ _bad_ if there are different points _b_ and _c_, not equal to _a_, from the given set such that angle between vectors and is acute (i.e. strictly less than ). Otherwise, the point is called _good_.
The angle between vectors and in 5-dimensional space is defined as , where is the scalar product and is length of .
Given the list of points, print the indices of the good points in ascending order.
## Input
The first line of input contains a single integer _n_ (1 ≤ _n_ ≤ 103) — the number of points.
The next _n_ lines of input contain five integers _a__i_, _b__i_, _c__i_, _d__i_, _e__i_ (|_a__i_|, |_b__i_|, |_c__i_|, |_d__i_|, |_e__i_| ≤ 103) — the coordinates of the i-th point. All points are distinct.
## Output
First, print a single integer _k_ — the number of good points.
Then, print _k_ integers, each on their own line — the indices of the good points in ascending order.
[samples]
## Note
In the first sample, the first point forms exactly a angle with all other pairs of points, so it is good.
In the second sample, along the cd plane, we can see the points look as follows:
We can see that all angles here are acute, so no points are good.
你被给定一个包含 #cf_span[n] 个点的集合，这些点位于五维空间中。点从 #cf_span[1] 到 #cf_span[n] 编号。任意两点不重合。
我们称点 #cf_span[a] 为 _坏点_，如果存在两个不同的点 #cf_span[b] 和 #cf_span[c]（均不等于 #cf_span[a]），使得向量 和 之间的夹角为锐角（即严格小于 ）。否则，该点称为 _好点_。
五维空间中向量 和 之间的夹角定义为 ，其中 是点积， 是向量 的长度。
给定这些点的列表，请按升序输出所有好点的编号。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 103]）——点的数量。
接下来的 #cf_span[n] 行，每行包含五个整数 #cf_span[ai, bi, ci, di, ei]（#cf_span[|ai|, |bi|, |ci|, |di|, |ei| ≤ 103]）——第 i 个点的坐标。所有点互不相同。
首先，输出一个整数 #cf_span[k] —— 好点的数量。
然后，输出 #cf_span[k] 个整数，每个占一行——按升序排列的好点的编号。
在第一个样例中，第一个点与所有其他点对形成的夹角恰好为 ，因此它是好点。
在第二个样例中，沿 cd 平面观察，这些点的分布如下：
我们可以看到，所有夹角均为锐角，因此没有好点。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 103]）——点的数量。接下来的 #cf_span[n] 行，每行包含五个整数 #cf_span[ai, bi, ci, di, ei]（#cf_span[|ai|, |bi|, |ci|, |di|, |ei| ≤ 103]）——第 i 个点的坐标。所有点互不相同。
## Output
首先，输出一个整数 #cf_span[k] —— 好点的数量。然后，输出 #cf_span[k] 个整数，每个占一行——按升序排列的好点的编号。
[samples]
## Note
在第一个样例中，第一个点与所有其他点对形成的夹角恰好为 ，因此它是好点。在第二个样例中，沿 cd 平面观察，这些点的分布如下：我们可以看到，所有夹角均为锐角，因此没有好点。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10^3 $, be the number of points.
Let $ P_i = (a_i, b_i, c_i, d_i, e_i) \in \mathbb{R}^5 $, $ i \in \{1, \dots, n\} $, be the coordinates of the $ i $-th point, with all $ P_i $ distinct.
For any distinct indices $ a, b, c \in \{1, \dots, n\} $ with $ a \ne b $, $ a \ne c $, define vectors:
$ \vec{u} = P_b - P_a $,
$ \vec{v} = P_c - P_a $.
The angle between $ \vec{u} $ and $ \vec{v} $ is acute if and only if $ \vec{u} \cdot \vec{v} > 0 $.
A point $ P_a $ is **bad** if there exist distinct $ b, c \in \{1, \dots, n\} \setminus \{a\} $ such that $ \vec{u} \cdot \vec{v} > 0 $.
Otherwise, $ P_a $ is **good**.
**Constraints**
1. $ 1 \leq n \leq 1000 $
2. For all $ i \in \{1, \dots, n\} $, $ |a_i|, |b_i|, |c_i|, |d_i|, |e_i| \leq 1000 $
3. $ P_i \ne P_j $ for all $ i \ne j $
**Objective**
Find the set $ G \subseteq \{1, \dots, n\} $ of indices $ a $ such that for all distinct $ b, c \in \{1, \dots, n\} \setminus \{a\} $,
$$
(P_b - P_a) \cdot (P_c - P_a) \leq 0
$$
Output $ |G| $, followed by the elements of $ G $ in ascending order.
API Response (JSON)
{
"problem": {
"name": "C. Five Dimensional Points",
"description": {
"content": "You are given set of _n_ points in 5-dimensional space. The points are labeled from 1 to _n_. No two points coincide. We will call point _a_ _bad_ if there are different points _b_ and _c_, not equal",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF851C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given set of _n_ points in 5-dimensional space. The points are labeled from 1 to _n_. No two points coincide.\n\nWe will call point _a_ _bad_ if there are different points _b_ and _c_, not equal...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个包含 #cf_span[n] 个点的集合，这些点位于五维空间中。点从 #cf_span[1] 到 #cf_span[n] 编号。任意两点不重合。\n\n我们称点 #cf_span[a] 为 _坏点_，如果存在两个不同的点 #cf_span[b] 和 #cf_span[c]（均不等于 #cf_span[a]），使得向量 和 之间的夹角为锐角（即严格小于 ）。否则，该点称为 _好点_。\n\n...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^3 $, be the number of points. \nLet $ P_i = (a_i, b_i, c_i, d_i, e_i) \\in \\mathbb{R}^5 $, $ i \\in \\{1, \\dots, n\\} $, be the coordinates o...",
"is_translate": false,
"language": "Formal"
}
]
}