A11692. Ghosts
编程题
普及/提高-
知识点
题目描述
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$ .
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.
输出格式
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.
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.
输入输出样例
输入 #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
说明/提示
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.
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.