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[a] 的不同点 #cf_span[b] 和 #cf_span[c]，使得向量 和 之间的夹角为锐角（即严格小于 ）。否则，该点称为 _好点_。
五维空间中向量 和 之间的夹角定义为 ，其中 是点积， 是向量的长度。
给定这些点的列表，请按升序输出所有好点的编号。
输入的第一行包含一个整数 #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 平面上，我们可以看到这些点的分布如下：
我们可以看到，所有夹角均为锐角，因此没有好点。
Let $ P = \{ \mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_n \} \subset \mathbb{R}^5 $ be a set of $ n $ distinct points in 5-dimensional space, where $ \mathbf{p}_i = (a_i, b_i, c_i, d_i, e_i) $.
For any three distinct indices $ a, b, c \in \{1, 2, \dots, n\} $, define the vectors:
$$
\vec{u} = \mathbf{p}_b - \mathbf{p}_a, \quad \vec{v} = \mathbf{p}_c - \mathbf{p}_a.
$$
The angle $ \theta $ between $ \vec{u} $ and $ \vec{v} $ is given by:
$$
\cos \theta = \frac{\vec{u} \cdot \vec{v}}{\|\vec{u}\| \cdot \|\vec{v}\|}.
$$
A point $ \mathbf{p}_a $ is **bad** if there exist distinct $ b, c \ne a $ such that $ \theta < \frac{\pi}{2} $, i.e., $ \vec{u} \cdot \vec{v} > 0 $.
A point $ \mathbf{p}_a $ is **good** if for all pairs of distinct indices $ b, c \ne a $, it holds that $ \vec{u} \cdot \vec{v} \leq 0 $.
---
**Given:**
- Integer $ n $, $ 1 \leq n \leq 10^3 $
- Points $ \mathbf{p}_1, \dots, \mathbf{p}_n \in \mathbb{R}^5 $, all distinct
**Objective:**
Find the set $ G \subseteq \{1, 2, \dots, n\} $ of indices $ a $ such that for all $ b, c \in \{1, \dots, n\} \setminus \{a\} $, $ b \ne c $,
$$
(\mathbf{p}_b - \mathbf{p}_a) \cdot (\mathbf{p}_c - \mathbf{p}_a) \leq 0.
$$
Output:
- $ k = |G| $
- The elements of $ G $ in ascending order
---
**Formal Output:**
Let $ G = \left\{ a \in \{1, \dots, n\} \;\middle|\; \forall b, c \in \{1, \dots, n\} \setminus \{a\},\; b \ne c:\; (\mathbf{p}_b - \mathbf{p}_a) \cdot (\mathbf{p}_c - \mathbf{p}_a) \leq 0 \right\} $.
Print $ |G| $, followed by the elements of $ G $ in ascending order.
API Response (JSON)
{
"problem": {
"name": "A. 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": "CF850A"
},
"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[a] 的不同点 #cf_span[b] 和 #cf_span[c]，使得向量 和 之间的夹角为锐角（即严格小于 ）。否则，该点称为 _好点_。\n\n五...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ P = \\{ \\mathbf{p}_1, \\mathbf{p}_2, \\dots, \\mathbf{p}_n \\} \\subset \\mathbb{R}^5 $ be a set of $ n $ distinct points in 5-dimensional space, where $ \\mathbf{p}_i = (a_i, b_i, c_i, d_i, e_i) $.\n\nFo...",
"is_translate": false,
"language": "Formal"
}
]
}