{"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 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_.\n\nThe angle between vectors and in 5-dimensional space is defined as , where is the scalar product and is length of .\n\nGiven the list of points, print the indices of the good points in ascending order.\n\n## Input\n\nThe first line of input contains a single integer _n_ (1 ≤ _n_ ≤ 103) — the number of points.\n\nThe 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.\n\n## Output\n\nFirst, print a single integer _k_ — the number of good points.\n\nThen, print _k_ integers, each on their own line — the indices of the good points in ascending order.\n\n[samples]\n\n## Note\n\nIn the first sample, the first point forms exactly a angle with all other pairs of points, so it is good.\n\nIn the second sample, along the cd plane, we can see the points look as follows:\n\n![image](https://espresso.codeforces.com/b47e1fa6958eae10e2164a9d9282fdcbcb92a857.png)\n\nWe can see that all angles here are acute, so no points are good.","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五维空间中向量  和  之间的夹角定义为 ，其中  是点积，  是向量的长度。\n\n给定这些点的列表，请按升序输出所有好点的编号。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 103]）——点的数量。\n\n接下来的 #cf_span[n] 行，每行包含五个整数 #cf_span[ai, bi, ci, di, ei]（#cf_span[|ai|, |bi|, |ci|, |di|, |ei| ≤ 103]）——表示第 i 个点的坐标。所有点互不相同。\n\n首先，输出一个整数 #cf_span[k] —— 好点的数量。\n\n然后，输出 #cf_span[k] 个整数，每个占一行，按升序排列的好点的编号。\n\n在第一个样例中，第一个点与所有其他点对形成的夹角恰好为 ，因此它是好点。\n\n在第二个样例中，在 cd 平面上，我们可以看到这些点的分布如下：\n\n我们可以看到，所有夹角均为锐角，因此没有好点。\n\n## Input\n\n输入的第一行包含一个整数 #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 个点的坐标。所有点互不相同。\n\n## Output\n\n首先，输出一个整数 #cf_span[k] —— 好点的数量。然后，输出 #cf_span[k] 个整数，每个占一行，按升序排列的好点的编号。\n\n[samples]\n\n## Note\n\n在第一个样例中，第一个点与所有其他点对形成的夹角恰好为 ，因此它是好点。在第二个样例中，在 cd 平面上，我们可以看到这些点的分布如下：\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\nFor any three distinct indices $ a, b, c \\in \\{1, 2, \\dots, n\\} $, define the vectors:\n$$\n\\vec{u} = \\mathbf{p}_b - \\mathbf{p}_a, \\quad \\vec{v} = \\mathbf{p}_c - \\mathbf{p}_a.\n$$\n\nThe angle $ \\theta $ between $ \\vec{u} $ and $ \\vec{v} $ is given by:\n$$\n\\cos \\theta = \\frac{\\vec{u} \\cdot \\vec{v}}{\\|\\vec{u}\\| \\cdot \\|\\vec{v}\\|}.\n$$\n\nA 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 $.\n\nA 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 $.\n\n---\n\n**Given:**  \n- Integer $ n $, $ 1 \\leq n \\leq 10^3 $  \n- Points $ \\mathbf{p}_1, \\dots, \\mathbf{p}_n \\in \\mathbb{R}^5 $, all distinct  \n\n**Objective:**  \nFind 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 $,  \n$$\n(\\mathbf{p}_b - \\mathbf{p}_a) \\cdot (\\mathbf{p}_c - \\mathbf{p}_a) \\leq 0.\n$$\n\nOutput:  \n- $ k = |G| $  \n- The elements of $ G $ in ascending order  \n\n--- \n\n**Formal Output:**\n\nLet $ 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\\} $.\n\nPrint $ |G| $, followed by the elements of $ G $ in ascending order.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF850A","tags":["brute force","geometry","math"],"sample_group":[["6\n0 0 0 0 0\n1 0 0 0 0\n0 1 0 0 0\n0 0 1 0 0\n0 0 0 1 0\n0 0 0 0 1","1\n1"],["3\n0 0 1 2 0\n0 0 9 2 0\n0 0 5 9 0","0"]],"created_at":"2026-03-03 11:00:39"}}