← 返回题目列表

Codeforces · 975/D

D. 鬼魂

中文机器翻译题面 查看原题

鬼魂生活在和谐与和平中,他们在太空中旅行没有任何目的,除了吓唬任何挡路的人。

宇宙中有$$$n$$$幽灵,它们在$$$OXY$$$平面上移动,每个幽灵都有自己不随时间变化的速度: $$$\overrightarrow{V} = V_{x}\overrightarrow{i} + V_{y}\overrightarrow{j}$$$ 其中$$$V_{x}$$$是其在平面上的速度$$$x$$$ 轴和 $$$V_{y}$$$ 位于 $$$y$$$ 轴上。

鬼$$$i$$$有经验值$$$EX_i$$$,这代表他过去有多少鬼试图吓唬他。如果两个鬼魂同时处于同一个笛卡尔点,就会互相吓唬。

由于鬼魂以匀速移动,一段时间后就不会再受到惊吓了(真是松了口气!)并且鬼魂 $$$GX = \sum_{i=1}^{n} EX_i$$$ 的经验永远不会增加。

Tameem 是一颗红巨星,他在 $$$T$$$ 的某个时刻拍摄了笛卡尔平面的照片,并且神奇地所有鬼魂都排列在 $$$y = a \cdot x + b$$$ 形式的线上。你要计算在无限的未来,鬼类$$$GX$$$的经验指数是多少,这就是你今天的任务。

请注意,当 Tameem 拍照时,$$$GX$$$ 可能已经大于 $$$0$$$,因为许多鬼魂可能在 $$$[-\infty, T]$$$ 之间的任何时刻互相吓到。

输入

第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n \leq 200000$$$, $$$1 \leq |a| \leq 10^9$$$, $$$0 \le |b| \le 10^9$$$) — 宇宙中鬼魂的数量直线的参数。

接下来的 $$$n$$$ 行包含三个整数 $$$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$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个幽灵的当前 $$$x$$$ 坐标(并且 $$$y_i = a \cdot x_i + b$$$)。

保证没有两个鬼魂共享相同的初始位置,换句话说,保证对于所有 $$$(i,j)$$$ $$$x_i \neq x_j$$$ 对于 $$$i \ne j$$$。

输出

输出一行:不定未来的鬼种经验指数$$$GX$$$。

示例

输入 #1

4 1 1
1 -1 -1
2 1 1
3 1 1
4 -1 -1

输出 #1

8

输入 #2

3 1 0
-1 1 0
0 0 -1
1 -1 -2

输出 #2

6

输入 #3

3 1 0
0 0 0
1 0 0
2 0 0

输出 #3

0

注意

有四次碰撞 $$$(1,2,T-0.5)$$$, $$$(1,3,T-1)$$$, $$$(2,4,T+1)$$$, $$$(3,4,T+0.5)$$$,其中 $$$(u,v,t)$$$ 表示幽灵 $$$u$$$ 和幽灵之间发生碰撞$$$v$$$ 此时$$$t$$$。每次碰撞,每个幽灵都会获得一个经验值,这意味着 $$$GX = 4 \cdot 2 = 8$$$。

在第二个测试中,当 $$$t = T + 1$$$ 时,所有点都会发生碰撞。

红色箭头代表第 1 个幽灵速度,橙色代表第 2 个幽灵速度,蓝色代表第 3 个幽灵速度。