Preparando MOJI
Ghosts live in harmony and peace, they travel the space without any purpose other than scare whoever stands in their way.
There 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.
A 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.
As 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.
Tameem 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.
Note 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]$$$.
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.
Each 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$$$).
It 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$$$.
Output one line: experience index of the ghost kind $$$GX$$$ in the indefinite future.
4 1 1
1 -1 -1
2 1 1
3 1 1
4 -1 -1
8
3 1 0
-1 1 0
0 0 -1
1 -1 -2
6
3 1 0
0 0 0
1 0 0
2 0 0
0
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$$$.
In the second test, all points will collide when $$$t = T + 1$$$.
The red arrow represents the 1-st ghost velocity, orange represents the 2-nd ghost velocity, and blue represents the 3-rd ghost velocity.
Informação
Provedor Codeforces
Código CF975D
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:33:53
Relacionados