D. Ghosts

幽灵们和谐共处，它们在宇宙中穿梭，唯一的目的是吓阻挡在它们前方的任何存在。 宇宙中有 $n$ 个幽灵，它们在 $O X Y$ 平面上移动，每个幽灵都有一个恒定不变的速度：$accent(V, arrow) = V_x accent(i, arrow) + V_y accent(j, arrow)$，其中 $V_x$ 是其在 $x$ 轴上的速度，$V_y$ 是其在 $y$ 轴上的速度。 幽灵 $i$ 拥有经验值 $E X_i$，表示过去有多少幽灵试图吓唬过它。两个幽灵在某一时刻位于同一笛卡尔点时，就会互相吓唬。 由于幽灵以恒定速度移动，经过一段时间后将不再发生进一步的吓唬（真是松了一口气！），幽灵族群的经验总和 $G X = sum_(i = 1)^n E X_i$ 将不再增加。 塔米姆是一位红巨星，他在某一时刻 $T$ 拍摄了笛卡尔平面的照片，神奇的是，所有幽灵都位于一条形如 $y = a dot.op x + b$ 的直线上。你需要计算在无限未来的某个时刻，幽灵族群的经验总和 $G X$ 将是多少，这就是你今天的任务。 注意：当塔米姆拍摄照片时，$G X$ 可能已经大于 $0$，因为在 $[ -infinity, T ]$ 的任意时刻，许多幽灵可能已经互相吓唬过。 第一行包含三个整数 $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$。 输出一行：无限未来中幽灵族群的经验总和 $G X$。 存在四次碰撞：$(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 个幽灵的速度。 ## Input 第一行包含三个整数 $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$。 ## Output 输出一行：无限未来中幽灵族群的经验总和 $G X$。 [samples] ## Note 存在四次碰撞：$(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 个幽灵的速度。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of ghosts. Let $ a, b \in \mathbb{R} $ define the line $ y = ax + b $ on which all ghosts are initially aligned at time $ T $. For each ghost $ i \in \{1, \dots, 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 $. - Let $ y_i = a x_i + b $ be its initial $ y $-coordinate. - Let $ \vec{v}_i = (v_{x,i}, v_{y,i}) \in \mathbb{R}^2 $ be its constant velocity vector. **Constraints** 1. $ 1 \le n \le 200000 $ 2. $ 1 \le |a| \le 10^9 $, $ 0 \le |b| \le 10^9 $ 3. $ -10^9 \le x_i \le 10^9 $, $ -10^9 \le v_{x,i}, v_{y,i} \le 10^9 $ 4. All $ x_i $ are distinct. **Objective** Compute 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 $). A collision occurs between ghosts $ i $ and $ j $ ($ i \ne j $) if there exists $ t \in \mathbb{R} $ such that: $$ x_i + v_{x,i}(t - T) = x_j + v_{x,j}(t - T) $$ $$ y_i + v_{y,i}(t - T) = y_j + v_{y,j}(t - T) $$ Since $ 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 $: $$ a x_i + b + v_{y,i}(t - T) = a x_j + b + v_{y,j}(t - T) \Rightarrow a(x_i - x_j) = (v_{y,j} - v_{y,i})(t - T) $$ From the $ x $-equation: $$ x_i - x_j = (v_{x,j} - v_{x,i})(t - T) \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{)} $$ Substitute into the $ y $-condition: $$ a(x_i - x_j) = (v_{y,j} - v_{y,i}) \cdot \frac{x_i - x_j}{v_{x,j} - v_{x,i}} \Rightarrow a = \frac{v_{y,j} - v_{y,i}}{v_{x,j} - v_{x,i}} \quad \text{(if } x_i \ne x_j \text{)} $$ Thus, ghosts $ i $ and $ j $ collide **if and only if**: $$ \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{)} $$ Define for each ghost $ i $: $$ c_i = v_{y,i} - a v_{x,i} $$ Then, ghosts $ i $ and $ j $ collide **iff** $ c_i = c_j $. Each such pair $ (i, j) $ with $ c_i = c_j $ contributes 2 to $ GX $ (one experience point per ghost). Let $ f(c) $ be the frequency of value $ c $ in the multiset $ \{c_1, \dots, c_n\} $. Then the total number of unordered pairs with the same $ c $ is $ \sum_{c} \binom{f(c)}{2} $, and each pair contributes 2 to $ GX $. Thus: $$ GX = 2 \sum_{c} \binom{f(c)}{2} = \sum_{c} f(c)(f(c) - 1) $$ **Output** $$ \boxed{GX = \sum_{c} f(c)(f(c) - 1)} $$ where $ f(c) $ is the number of ghosts with $ c_i = c = v_{y,i} - a v_{x,i} $.