{"raw_statement":[{"iden":"statement","content":"Ghosts live in harmony and peace, they travel the space without any purpose other than scare whoever stands in their way.\n\nThere are $n$ ghosts in the universe, they move in the $OXY$ plane, each one of them has its own velocity that does not change in time: $\\overrightarrow{V} = V_{x}\\overrightarrow{i} + V_{y}\\overrightarrow{j}$ where $V_{x}$ is its speed on the $x$\\-axis and $V_{y}$ is on the $y$\\-axis.\n\nA ghost $i$ has experience value $EX_i$, which represent how many ghosts tried to scare him in his past. Two ghosts scare each other if they were in the same cartesian point at a moment of time.\n\nAs the ghosts move with constant speed, after some moment of time there will be no further scaring (_what a relief!_) and the experience of ghost kind $GX = \\sum_{i=1}^{n} EX_i$ will never increase.\n\nTameem is a red giant, he took a picture of the cartesian plane at a certain moment of time $T$, and magically all the ghosts were aligned on a line of the form $y = a \\cdot x + b$. You have to compute what will be the experience index of the ghost kind $GX$ in the indefinite future, this is your task for today.\n\nNote that when Tameem took the picture, $GX$ may already be greater than $0$, because many ghosts may have scared one another at any moment between $[-\\infty, T]$."},{"iden":"input","content":"The first line contains three integers $n$, $a$ and $b$ ($1 \\leq n \\leq 200000$, $1 \\leq |a| \\leq 10^9$, $0 \\le |b| \\le 10^9$) — the number of ghosts in the universe and the parameters of the straight line.\n\nEach of the next $n$ lines contains three integers $x_i$, $V_{xi}$, $V_{yi}$ ($-10^9 \\leq x_i \\leq 10^9$, $-10^9 \\leq V_{x i}, V_{y i} \\leq 10^9$), where $x_i$ is the current $x$\\-coordinate of the $i$\\-th ghost (and $y_i = a \\cdot x_i + b$).\n\nIt is guaranteed that no two ghosts share the same initial position, in other words, it is guaranteed that for all $(i,j)$ $x_i \\neq x_j$ for $i \\ne j$."},{"iden":"output","content":"Output one line: experience index of the ghost kind $GX$ in the indefinite future."},{"iden":"examples","content":"Input\n\n4 1 1\n1 -1 -1\n2 1 1\n3 1 1\n4 -1 -1\n\nOutput\n\n8\n\nInput\n\n3 1 0\n-1 1 0\n0 0 -1\n1 -1 -2\n\nOutput\n\n6\n\nInput\n\n3 1 0\n0 0 0\n1 0 0\n2 0 0\n\nOutput\n\n0"},{"iden":"note","content":"There are four collisions $(1,2,T-0.5)$, $(1,3,T-1)$, $(2,4,T+1)$, $(3,4,T+0.5)$, where $(u,v,t)$ means a collision happened between ghosts $u$ and $v$ at moment $t$. At each collision, each ghost gained one experience point, this means that $GX = 4 \\cdot 2 = 8$.\n\nIn the second test, all points will collide when $t = T + 1$.\n\n<center>![image](https://espresso.codeforces.com/632930388686f4065fba42f9dba9a1c12c028844.png)</center>The red arrow represents the 1-st ghost velocity, orange represents the 2-nd ghost velocity, and blue represents the 3-rd ghost velocity."}],"translated_statement":[{"iden":"statement","content":"幽灵们和谐共处，它们在宇宙中穿梭，唯一的目的是吓阻挡在它们前方的任何存在。\n\n宇宙中有 $n$ 个幽灵，它们在 $O X Y$ 平面上移动，每个幽灵都有一个恒定不变的速度：$accent(V, arrow) = V_x accent(i, arrow) + V_y accent(j, arrow)$，其中 $V_x$ 是其在 $x$ 轴上的速度，$V_y$ 是其在 $y$ 轴上的速度。\n\n幽灵 $i$ 拥有经验值 $E X_i$，表示过去有多少幽灵试图吓唬过它。两个幽灵在某一时刻位于同一笛卡尔点时，就会互相吓唬。\n\n由于幽灵以恒定速度移动，经过一段时间后将不再发生进一步的吓唬（真是松了一口气！），幽灵族群的经验总和 $G X = sum_(i = 1)^n E X_i$ 将不再增加。\n\n塔米姆是一位红巨星，他在某一时刻 $T$ 拍摄了笛卡尔平面的照片，神奇的是，所有幽灵都位于一条形如 $y = a dot.op x + b$ 的直线上。你需要计算在无限未来的某个时刻，幽灵族群的经验总和 $G X$ 将是多少，这就是你今天的任务。\n\n注意：当塔米姆拍摄照片时，$G X$ 可能已经大于 $0$，因为在 $[ -infinity, T ]$ 的任意时刻，许多幽灵可能已经互相吓唬过。\n\n第一行包含三个整数 $n$, $a$ 和 $b$（$1 lt.eq n lt.eq 200000$，$1 lt.eq | a | lt.eq 10^9$，$0 lt.eq | b | lt.eq 10^9$）——宇宙中幽灵的数量和直线的参数。\n\n接下来的 $n$ 行每行包含三个整数 $x_i$, $V_(x i)$, $V_(y i)$（$-10^9 lt.eq x_i lt.eq 10^9$，$-10^9 lt.eq V_(x i), V_(y i) lt.eq 10^9$），其中 $x_i$ 是第 $i$ 个幽灵当前的 $x$ 坐标（且 $y_i = a dot.op x_i + b$）。\n\n保证没有两个幽灵具有相同的初始位置，即对于所有 $(i, j)$，当 $i != j$ 时，$x_i eq.not x_j$。\n\n输出一行：无限未来中幽灵族群的经验总和 $G X$。\n\n存在四次碰撞：$(1, 2, T -0. 5)$、$(1, 3, T -1)$、$(2, 4, T + 1)$、$(3, 4, T + 0. 5)$，其中 $(u, v, t)$ 表示幽灵 $u$ 和 $v$ 在时刻 $t$ 发生碰撞。每次碰撞中，每个幽灵获得一个经验点，因此 $G X = 4 dot.op 2 = 8$。\n\n在第二个测试用例中，所有点将在 $t = T + 1$ 时发生碰撞。\n\n红色箭头表示第 1 个幽灵的速度，橙色表示第 2 个幽灵的速度，蓝色表示第 3 个幽灵的速度。"},{"iden":"input","content":"第一行包含三个整数 $n$, $a$ 和 $b$（$1 lt.eq n lt.eq 200000$，$1 lt.eq | a | lt.eq 10^9$，$0 lt.eq | b | lt.eq 10^9$）——宇宙中幽灵的数量和直线的参数。接下来的 $n$ 行每行包含三个整数 $x_i$, $V_(x i)$, $V_(y i)$（$-10^9 lt.eq x_i lt.eq 10^9$，$-10^9 lt.eq V_(x i), V_(y i) lt.eq 10^9$），其中 $x_i$ 是第 $i$ 个幽灵当前的 $x$ 坐标（且 $y_i = a dot.op x_i + b$）。保证没有两个幽灵具有相同的初始位置，即对于所有 $(i, j)$，当 $i != j$ 时，$x_i eq.not x_j$。"},{"iden":"output","content":"输出一行：无限未来中幽灵族群的经验总和 $G X$。"},{"iden":"examples","content":"输入\n4 1 1\n1 -1 -1\n2 1 1\n3 1 1\n4 -1 -1\n输出\n8\n\n输入\n3 1 0\n-1 1 0\n0 0 -1\n1 -1 -2\n输出\n6\n\n输入\n3 1 0\n0 0 0\n1 0 0\n2 0 0\n输出\n0"},{"iden":"note","content":"存在四次碰撞：$(1, 2, T -0. 5)$、$(1, 3, T -1)$、$(2, 4, T + 1)$、$(3, 4, T + 0. 5)$，其中 $(u, v, t)$ 表示幽灵 $u$ 和 $v$ 在时刻 $t$ 发生碰撞。每次碰撞中，每个幽灵获得一个经验点，因此 $G X = 4 dot.op 2 = 8$。在第二个测试用例中，所有点将在 $t = T + 1$ 时发生碰撞。红色箭头表示第 1 个幽灵的速度，橙色表示第 2 个幽灵的速度，蓝色表示第 3 个幽灵的速度。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of ghosts.  \nLet $ a, b \\in \\mathbb{R} $ define the line $ y = ax + b $ on which all ghosts are initially aligned at time $ T $.  \nFor each ghost $ i \\in \\{1, \\dots, n\\} $:  \n- Let $ x_i \\in \\mathbb{R} $ be its initial $ x $-coordinate at time $ T $, with $ x_i \\ne x_j $ for $ i \\ne j $.  \n- Let $ y_i = a x_i + b $ be its initial $ y $-coordinate.  \n- Let $ \\vec{v}_i = (v_{x,i}, v_{y,i}) \\in \\mathbb{R}^2 $ be its constant velocity vector.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 200000 $  \n2. $ 1 \\le |a| \\le 10^9 $, $ 0 \\le |b| \\le 10^9 $  \n3. $ -10^9 \\le x_i \\le 10^9 $, $ -10^9 \\le v_{x,i}, v_{y,i} \\le 10^9 $  \n4. All $ x_i $ are distinct.  \n\n**Objective**  \nCompute the total experience index $ GX = \\sum_{i=1}^n EX_i $, where $ EX_i $ is the number of ghosts that have collided with ghost $ i $ at any time $ t \\in \\mathbb{R} $ (including $ t \\le T $).  \n\nA collision occurs between ghosts $ i $ and $ j $ ($ i \\ne j $) if there exists $ t \\in \\mathbb{R} $ such that:  \n$$\nx_i + v_{x,i}(t - T) = x_j + v_{x,j}(t - T)\n$$\n$$\ny_i + v_{y,i}(t - T) = y_j + v_{y,j}(t - T)\n$$\n\nSince $ y_i = a x_i + b $ and $ y_j = a x_j + b $, the second equation is redundant if the first holds and the velocities satisfy the collinearity condition. Substituting $ y_i, y_j $:  \n$$\na x_i + b + v_{y,i}(t - T) = a x_j + b + v_{y,j}(t - T)\n\\Rightarrow a(x_i - x_j) = (v_{y,j} - v_{y,i})(t - T)\n$$\n\nFrom the $ x $-equation:  \n$$\nx_i - x_j = (v_{x,j} - v_{x,i})(t - T)\n\\Rightarrow t - T = \\frac{x_i - x_j}{v_{x,j} - v_{x,i}} \\quad \\text{(if } v_{x,i} \\ne v_{x,j}\\text{)}\n$$\n\nSubstitute into the $ y $-condition:  \n$$\na(x_i - x_j) = (v_{y,j} - v_{y,i}) \\cdot \\frac{x_i - x_j}{v_{x,j} - v_{x,i}}\n\\Rightarrow a = \\frac{v_{y,j} - v_{y,i}}{v_{x,j} - v_{x,i}} \\quad \\text{(if } x_i \\ne x_j \\text{)}\n$$\n\nThus, ghosts $ i $ and $ j $ collide **if and only if**:  \n$$\n\\frac{v_{y,i} - v_{y,j}}{v_{x,i} - v_{x,j}} = a \\quad \\text{(i.e., } v_{y,i} - a v_{x,i} = v_{y,j} - a v_{x,j} \\text{)}\n$$\n\nDefine for each ghost $ i $:  \n$$\nc_i = v_{y,i} - a v_{x,i}\n$$\n\nThen, ghosts $ i $ and $ j $ collide **iff** $ c_i = c_j $.  \n\nEach such pair $ (i, j) $ with $ c_i = c_j $ contributes 2 to $ GX $ (one experience point per ghost).  \n\nLet $ f(c) $ be the frequency of value $ c $ in the multiset $ \\{c_1, \\dots, c_n\\} $.  \nThen the total number of unordered pairs with the same $ c $ is $ \\sum_{c} \\binom{f(c)}{2} $, and each pair contributes 2 to $ GX $.  \n\nThus:  \n$$\nGX = 2 \\sum_{c} \\binom{f(c)}{2} = \\sum_{c} f(c)(f(c) - 1)\n$$\n\n**Output**  \n$$\n\\boxed{GX = \\sum_{c} f(c)(f(c) - 1)}\n$$  \nwhere $ f(c) $ is the number of ghosts with $ c_i = c = v_{y,i} - a v_{x,i} $.","simple_statement":null,"has_page_source":false}