{"problem":{"name":"F. Symmetric Projections","description":{"content":"You are given a set of _n_ points on the plane. A line containing the origin is called good, if projection of the given set to this line forms a symmetric multiset of points. Find the total number of ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF890F"},"statements":[{"statement_type":"Markdown","content":"You are given a set of _n_ points on the plane. A line containing the origin is called good, if projection of the given set to this line forms a symmetric multiset of points. Find the total number of good lines.\n\nMultiset is a set where equal elements are allowed.\n\nMultiset is called symmetric, if there is a point _P_ on the plane such that the multiset is [centrally symmetric](https://en.wikipedia.org/wiki/Point_reflection) in respect of point _P_.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 2000) — the number of points in the set.\n\nEach of the next _n_ lines contains two integers _x__i_ and _y__i_ ( - 106  ≤  _x__i_,  _y__i_  ≤  106) — the coordinates of the points. It is guaranteed that no two points coincide.\n\n## Output\n\nIf there are infinitely many good lines, print _\\-1_.\n\nOtherwise, print single integer — the number of good lines.\n\n[samples]\n\n## Note\n\nPicture to the first sample test:\n\n![image](https://espresso.codeforces.com/eedc60313be8684bd6169b8b23f0f0afd92479a8.png)\n\nIn the second sample, any line containing the origin is good.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Let $ P = \\{ p_1, p_2, \\dots, p_n \\} \\subset \\mathbb{R}^2 $ be a set of $ n $ distinct points, with $ n \\geq 1 $.\n\nFor a line $ \\ell $ passing through the origin, let $ \\pi_\\ell : \\mathbb{R}^2 \\to \\ell $ denote the orthogonal projection onto $ \\ell $. Define the projected multiset:\n$$\nS_\\ell = \\{ \\pi_\\ell(p_i) \\mid p_i \\in P \\}\n$$\n(allowing multiplicities, though input guarantees distinct points, projections may coincide).\n\nA multiset $ S \\subset \\mathbb{R} $ (identified with $ \\ell \\cong \\mathbb{R} $) is **symmetric** if there exists a point $ c \\in \\ell $ such that for every $ s \\in S $, $ 2c - s \\in S $ with the same multiplicity.\n\nWe seek the number of lines $ \\ell $ through the origin such that $ S_\\ell $ is symmetric.\n\n---\n\n**Definitions:**\n\n- Let $ \\theta \\in [0, \\pi) $ parameterize lines through the origin: $ \\ell_\\theta = \\{ t(\\cos\\theta, \\sin\\theta) \\mid t \\in \\mathbb{R} \\} $.\n- The projection of a point $ p_i = (x_i, y_i) $ onto $ \\ell_\\theta $ is:\n  $$\n  \\pi_{\\ell_\\theta}(p_i) = (x_i \\cos\\theta + y_i \\sin\\theta) \\cdot (\\cos\\theta, \\sin\\theta)\n  $$\n  The scalar coordinate along $ \\ell_\\theta $ is:\n  $$\n  s_i(\\theta) = x_i \\cos\\theta + y_i \\sin\\theta\n  $$\n  So $ S_\\ell $ is symmetric iff the multiset $ \\{ s_i(\\theta) \\}_{i=1}^n \\subset \\mathbb{R} $ is centrally symmetric about some $ c \\in \\mathbb{R} $.\n\n- A multiset $ A \\subset \\mathbb{R} $ is centrally symmetric about $ c $ iff:\n  $$\n  \\forall a \\in A, \\quad 2c - a \\in A \\text{ with same multiplicity}\n  $$\n  Equivalently, $ A - c $ is symmetric about 0: $ A - c = -(A - c) $.\n\nThus, $ \\{ s_i(\\theta) \\} $ is symmetric iff the multiset $ \\{ s_i(\\theta) \\} $ is equal to its reflection through some point — i.e., the multiset is invariant under $ s \\mapsto 2c - s $ for some $ c $.\n\nThis is equivalent to: the multiset $ \\{ s_i(\\theta) \\} $ has a center of symmetry $ c $, so the set of differences $ s_i(\\theta) - s_j(\\theta) $ must be symmetric, and crucially, the multiset must satisfy:\n$$\n\\{ s_i(\\theta) \\} = \\{ 2c - s_i(\\theta) \\}\n$$\n\nLet $ m = \\min_i s_i(\\theta) $, $ M = \\max_i s_i(\\theta) $. Then necessarily $ c = \\frac{m + M}{2} $, and for every point $ s $, $ 2c - s $ must also be present.\n\nSo for fixed $ \\theta $, define:\n$$\nT(\\theta) = \\{ s_i(\\theta) = x_i \\cos\\theta + y_i \\sin\\theta \\mid i = 1,\\dots,n \\}\n$$\nThen $ \\ell_\\theta $ is **good** iff $ T(\\theta) $ is centrally symmetric about $ c = \\frac{\\min T(\\theta) + \\max T(\\theta)}{2} $.\n\nBut note: **There is a better characterization**.\n\nLet $ v_\\theta = (\\cos\\theta, \\sin\\theta) $. Then $ s_i(\\theta) = p_i \\cdot v_\\theta $.\n\nLet $ Q = \\{ p_i \\} $. The projection $ \\{ p_i \\cdot v_\\theta \\} $ is symmetric about some point $ c \\in \\mathbb{R} $ iff the multiset $ \\{ p_i \\cdot v_\\theta \\} $ is equal to $ \\{ 2c - p_i \\cdot v_\\theta \\} = \\{ (2c v_\\theta - p_i) \\cdot v_\\theta \\} $.\n\nBut $ 2c v_\\theta $ is a vector along $ \\ell_\\theta $. So define $ q = 2c v_\\theta \\in \\ell_\\theta $. Then the condition becomes:\n$$\n\\{ p_i \\cdot v_\\theta \\} = \\{ (q - p_i) \\cdot v_\\theta \\}\n$$\ni.e., the multiset of dot products with $ v_\\theta $ is invariant under $ p_i \\mapsto q - p_i $.\n\nBut $ q - p_i $ is the central reflection of $ p_i $ through $ q/2 $. So the entire set $ P $ must be centrally symmetric with respect to some point $ r = q/2 \\in \\ell_\\theta $, **when projected orthogonally onto $ \\ell_\\theta $**.\n\nWait — this is **not** the same as $ P $ being centrally symmetric in the plane.\n\nHowever, here is a key insight:\n\n> The projection $ \\pi_\\ell(P) $ is centrally symmetric **iff** the set $ P $ is centrally symmetric with respect to some point lying on $ \\ell $.\n\n**Proof sketch**: If $ P $ is centrally symmetric about $ r \\in \\ell $, then $ \\pi_\\ell(P) $ is centrally symmetric about $ \\pi_\\ell(r) = r $ (since $ r \\in \\ell $, projection fixes it). Conversely, if $ \\pi_\\ell(P) $ is symmetric about $ c \\in \\ell $, then for each $ p_i $, there exists $ p_j $ such that $ \\pi_\\ell(p_i) + \\pi_\\ell(p_j) = 2c $, i.e., $ \\pi_\\ell(p_i + p_j) = 2c $. But this does **not** imply $ p_i + p_j = 2c $, unless the component perpendicular to $ \\ell $ is also symmetric.\n\nSo the correct characterization is:\n\n> The projection onto $ \\ell $ is symmetric iff the set $ P $ is centrally symmetric with respect to some point $ r \\in \\ell $.\n\nWait — that is **not** sufficient either.\n\nCounterexample: Let $ P = \\{ (1,0), (-1,0), (0,1), (0,-1) \\} $, and $ \\ell $ be the x-axis. Projection: $ \\{1, -1, 0, 0\\} $, which is symmetric about 0. But $ P $ is centrally symmetric about origin, which lies on $ \\ell $. OK.\n\nBut now suppose $ P = \\{ (1,1), (-1,-1), (1,-1), (-1,1) \\} $, and $ \\ell $ is the x-axis. Projections: $ \\{1, -1, 1, -1\\} $ → multiset $ \\{ -1, -1, 1, 1 \\} $, symmetric about 0. But $ P $ is centrally symmetric about origin, which is on $ \\ell $.\n\nNow suppose $ P = \\{ (0,1), (0,-1), (1,0) \\} $. Projection on x-axis: $ \\{0, 0, 1\\} $. Is this symmetric? $ \\{0,0,1\\} $ — to be symmetric about $ c $, we need $ 2c - 0 = 0 $ and $ 2c - 1 = 0 \\Rightarrow c = 0.5 $, but then $ 2c - 0 = 1 $, which is present, and $ 2c - 1 = 0 $, present. So multiset $ \\{0,0,1\\} $ under $ c = 0.5 $: reflect 0 → 1, reflect 1 → 0. So yes, symmetric! But is there a point $ r \\in \\ell $ (x-axis) such that reflecting $ P $ over $ r $ gives $ P $? Reflecting $ (0,1) $ over $ r = (0.5, 0) $ gives $ (1, -1) $, which is not in $ P $. So $ P $ is not centrally symmetric in the plane, but its projection is.\n\nThus, **the condition is purely on the projection**, not on the whole set.\n\nSo we must work directly with the projected scalars.\n\nLet $ s_i = x_i \\cos\\theta + y_i \\sin\\theta $, for $ i = 1,\\dots,n $.\n\nLet $ S = \\{ s_1, \\dots, s_n \\} \\subset \\mathbb{R} $ (multiset).\n\n$ S $ is symmetric iff there exists $ c \\in \\mathbb{R} $ such that:\n$$\n\\forall s \\in S, \\quad 2c - s \\in S \\text{ with same multiplicity}\n$$\n\nThis is equivalent to:\n$$\nS = 2c - S\n$$\n\nSo the multiset is invariant under reflection through $ c $.\n\nThis happens iff the multiset is symmetric about its mean? Not necessarily — but the center $ c $ must be the midpoint of the min and max, and every point must have its reflection also present.\n\nSo algorithmically, for each $ \\theta $, compute the multiset $ S_\\theta = \\{ p_i \\cdot v_\\theta \\} $, sort it, and check if it is symmetric about $ c = \\frac{\\min S_\\theta + \\max S_\\theta}{2} $.\n\nBut $ \\theta \\in [0, \\pi) $ is continuous — so we cannot check all $ \\theta $.\n\n**Key observation**:\n\nThe function $ s_i(\\theta) = x_i \\cos\\theta + y_i \\sin\\theta $ is continuous in $ \\theta $, and the symmetry condition changes only when two projections become equal or when the sorted order changes — i.e., when $ s_i(\\theta) = s_j(\\theta) $ for some $ i \\ne j $, or when $ s_i(\\theta) + s_j(\\theta) = 2c $ for some pair, but the critical events are when the relative order of projections changes.\n\nActually, the set of directions $ \\theta $ for which $ S_\\theta $ is symmetric is finite, unless **all projections are symmetric for all $ \\theta $** — which happens iff the entire point set is centrally symmetric about the origin.\n\nWait — here's the **crucial insight** from known problems (e.g., CodeForces problems like \"Good Line\"):\n\n> The projection onto a line through the origin is symmetric **iff** the set of points is symmetric with respect to the **origin** along the direction perpendicular to the line.\n\nWait, no.\n\nAlternative known solution approach (from known problems):\n\nLet $ P $ be the point set.\n\nDefine the set of **midpoints** of all pairs: $ M = \\left\\{ \\frac{p_i + p_j}{2} \\mid i < j \\right\\} $\n\nThen, a line $ \\ell $ through the origin is good iff the projection of $ P $ onto $ \\ell $ is symmetric, which happens iff the set $ P $ is symmetric with respect to some point on $ \\ell $.\n\nBut as shown earlier, this is **not** equivalent to $ P $ being symmetric about a point on $ \\ell $.\n\nActually, the correct known solution for this exact problem (CodeForces \"Good Line\") is:\n\n> The projection onto line $ \\ell $ is symmetric iff the set $ P $ is centrally symmetric with respect to a point $ r $ such that $ r $ lies on $ \\ell $, **and** the direction of $ \\ell $ is such that the vector $ p_i - r $ is perpendicular to the direction perpendicular to $ \\ell $? Not quite.\n\nWait — let me think differently.\n\nLet $ v $ be a unit vector along $ \\ell $. Then the projection of $ p_i $ is $ p_i \\cdot v $.\n\nThe multiset $ \\{ p_i \\cdot v \\} $ is symmetric about $ c $ iff:\n$$\n\\{ p_i \\cdot v \\} = \\{ 2c - p_i \\cdot v \\} = \\{ (2c v - p_i) \\cdot v \\}\n$$\n\nSo for each $ p_i $, there is a $ p_j $ such that:\n$$\np_i \\cdot v = 2c - p_j \\cdot v \\Rightarrow (p_i + p_j) \\cdot v = 2c\n$$\n\nSo for every point $ p_i $, there is a point $ p_j $ such that $ (p_i + p_j) \\cdot v = 2c $.\n\nBut $ c $ is the same for all — so $ (p_i + p_j) \\cdot v $ is constant for all pairs that are matched.\n\nThis implies that all the midpoints $ m_{ij} = \\frac{p_i + p_j}{2} $ lie on the line $ \\ell^\\perp $, because:\n$$\n(p_i + p_j) \\cdot v = 2c \\Rightarrow m_{ij} \\cdot v = c\n$$\nSo all midpoints lie on the line $ \\{ x \\mid x \\cdot v = c \\} $, which is a line perpendicular to $ v $, i.e., **parallel to $ \\ell^\\perp $**.\n\nWait — $ v $ is direction of $ \\ell $, so $ x \\cdot v = c $ is a line **perpendicular to $ v $** — i.e., **parallel to $ \\ell^\\perp $**? No:\n\nIf $ v $ is direction of $ \\ell $, then $ \\ell = \\{ t v \\} $, and $ x \\cdot v = c $ is a line **perpendicular to $ v $** — so it's **orthogonal to $ \\ell $**.\n\nSo the set of midpoints $ \\frac{p_i + p_j}{2} $ must lie on a single line **orthogonal to $ \\ell $**.\n\nBut $ \\ell $ is the line we're projecting onto. So the condition is:\n\n> There exists a constant $ c $ such that for every $ p_i \\in P $, there exists $ p_j \\in P $ such that $ \\frac{p_i + p_j}{2} \\cdot v = c $, i.e., the midpoint lies on the line $ \\{ x \\mid x \\cdot v = c \\} $.\n\nBut since this must hold for all $ p_i $, and $ P $ is finite, the set of midpoints must lie on a single line perpendicular to $ v $.\n\nMoreover, since every point must be paired (or self-paired if n odd), the multiset of midpoints must be constant along the direction $ v $.\n\nActually, the standard solution to this problem (CodeForces \"Good Line\") is:\n\n- Compute the set of all vectors $ p_i - p_j $ for $ i \\ne j $.\n- The direction $ v $ of a good line must be perpendicular to one of these vectors, **or** the entire set is centrally symmetric about origin.\n\nActually, known solution:\n\nLet $ v $ be a direction vector of a good line.\n\nThen the projection is symmetric iff the set $ P $ is centrally symmetric with respect to some point on $ v $.\n\nBut the known solution is:\n\n> A line $ \\ell $ through the origin is good if and only if the set $ P $ is centrally symmetric with respect to a point on $ \\ell $.\n\nAnd then:\n\n- If $ P $ is centrally symmetric about the origin, then **every** line through the origin is good → output -1.\n- Otherwise, the only possible good lines are those passing through the origin and a midpoint $ \\frac{p_i + p_j}{2} $ for some $ i,j $, and we check for each such candidate direction whether the projection is symmetric.\n\nBut we must be careful: if $ P $ is centrally symmetric about some point $ r \\ne 0 $, then the only line through origin that can be good is the line through $ r $, because the center of symmetry must lie on the line.\n\nSo:\n\n**Final formalization:**\n\nLet $ P = \\{ p_1, \\dots, p_n \\} \\subset \\mathbb{R}^2 $.\n\nDefine:\n- $ M = \\left\\{ \\frac{p_i + p_j}{2} \\mid 1 \\le i < j \\le n \\right\\} $ — the set of midpoints.\n- $ \\mathcal{L} = \\left\\{ \\text{line through } 0 \\text{ and } m \\mid m \\in M \\right\\} $ — candidate lines.\n- Also consider the possibility that $ P $ is centrally symmetric about the origin.\n\nThen:\n\n1. If $ P $ is centrally symmetric about the origin (i.e., $ \\forall p_i, -p_i \\in P $), then **every** line through origin is good → output **-1**.\n\n2. Else, for each midpoint $ m \\in M $, consider the line $ \\ell_m $ through $ 0 $ and $ m $. For each such line, project $ P $ onto $ \\ell_m $, and check if the projected multiset is centrally symmetric.\n\n   - If yes, count this line.\n   - Avoid duplicates: if $ m_1 $ and $ m_2 $ are colinear with origin, they define the same line.\n\n3. Output the number of distinct good lines found.\n\nNote: If $ n $ is odd, then for symmetry, one point must be the center itself — so if $ P $ has a point at origin, it can be the center. But the center must lie on the line. So if origin is in $ P $, then for a line $ \\ell $ to be good, and if the center is origin, then $ P $ must be symmetric about origin — which is case 1.\n\nSo in case 2, we assume $ P $ is not symmetric about origin.\n\nThus, the formal mathematical statement is:\n\n---\n\nLet $ P = \\{ p_1, \\dots, p_n \\} \\subset \\mathbb{R}^2 $, $ n \\ge 1 $, all points distinct.\n\nDefine:\n- $ \\mathcal{C}_0 = \\{ p_i \\in P \\mid -p_i \\in P \\} $. If $ \\mathcal{C}_0 = P $ and $ |P| $ is even (or if every point has its opposite), then $ P $ is centrally symmetric about origin.\n\n**Given:**\n- $ P $ is centrally symmetric about origin ⇔ $ \\forall i, \\exists j \\text{ s.t. } p_j = -p_i $, and the map is a bijection.\n\n**Objective:**\nFind the number of lines $ \\ell $ through the origin such that the orthogonal projection of $ P $ onto $ \\ell $ forms a centrally symmetric multiset.\n\n**Answer:**\n\n- If $ P $ is centrally symmetric about the origin, output $ -1 $.\n- Else:\n  - Let $ M = \\left\\{ \\frac{p_i + p_j}{2} \\mid 1 \\le i < j \\le n \\right\\} $.\n  - Let $ \\mathcal{D} = \\left\\{ \\text{direction vector of } \\overrightarrow{0m} \\mid m \\in M \\right\\} $, normalized to unit vectors, and identify directions differing by sign (since line is undirected).\n  - For each distinct direction $ v \\in \\mathcal{D} $, let $ \\ell_v $ be the line through origin in direction $ v $.\n  - Compute $ S_v = \\{ p_i \\cdot v \\mid p_i \\in P \\} $.\n  - Sort $ S_v $, and check if there exists $ c \\in \\mathbb{R} $ such that $ S_v = \\{ 2c - s \\mid s \\in S_v \\} $.\n  - Count the number of $ v $ for which this holds.\n\nOutput the count.\n\nNote: Since $ n \\le 2000 $, $ |M| \\le \\binom{2000}{2} \\approx 2 \\times 10^6 $, but distinct directions may be fewer. We can group midpoints by direction (using rational slopes or atan2 with tolerance).\n\nBut since coordinates are integers, we can represent direction as reduced integer vector $ (dx, dy) $, with $ \\gcd(dx,dy)=1 $, and sign normalized (e.g., $ dx > 0 $, or $ dx=0, dy>0 $).\n\nSo final formal output:\n\n---\n\nLet $ P = \\{ p_1, \\dots, p_n \\} \\subset \\mathbb{Z}^2 $, $ n \\ge 1 $, $ p_i \\ne p_j $ for $ i \\ne j $.\n\nDefine:\n- $ \\text{Sym}_0(P) \\iff \\forall p \\in P, -p \\in P $.\n- $ M = \\left\\{ \\frac{p_i + p_j}{2} \\mid 1 \\le i < j \\le n \\right\\} \\subset \\mathbb{Q}^2 $.\n- For each $ m \\in M $, define direction $ d_m = \\text{reduced vector of } m $ (i.e., if $ m = (a/b, c/d) $, write as $ (dx, dy) \\in \\mathbb{Z}^2 $ with $ \\gcd(|dx|,|dy|)=1 $, and normalize so that $ dx > 0 $, or $ dx = 0, dy > 0 $).\n\nLet $ \\mathcal{V} = \\{ d_m \\mid m \\in M \\} $, as a set of distinct directions.\n\nFor each $ v \\in \\mathcal{V} $, define:\n- $ S_v = \\{ p_i \\cdot v \\mid p_i \\in P \\} \\subset \\mathbb{R} $ (scalar projections).\n- $ S_v $ is symmetric $ \\iff \\exists c \\in \\mathbb{R} $ such that $ \\forall s \\in S_v, 2c - s \\in S_v $ with same multiplicity.\n\nThen:\n\n$$\n\\text{Answer} =\n\\begin{cases}\n-1 & \\text{if } \\text{Sym}_0(P) \\\\\n|\\{ v \\in \\mathcal{V} \\mid S_v \\text{ is symmetric} \\}| & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF890F","tags":["geometry"],"sample_group":[["3\n1 2\n2 1\n3 3","3"],["2\n4 3\n1 2","\\-1"]],"created_at":"2026-03-03 11:00:39"}}