ZOJ Problem Set - 4012
Your bridge is under attack! DreamGrid is launching an attack on BaoBao's town in the game Defense of the Bridges (DotB). The town receives \(n\) attacks and there are \(m\) bridges in the town in total. The \(i\)-th attack happens at point \((x_i, y_i)\), and the \(j\)-th bridge can be considered as a straight line on an 2D plane connecting \((a_j, 0)\) and \((0, b_j)\).
Time is limited, but BaoBao still has to check the number of attacks each bridge receives. Please help BaoBao finish this task.
We say a bridge connecting \((a_j, 0)\) and \((0, b_j)\) receives an attack happens at \((x_i, y_i)\), if and onlny if \((x_i, y_i)\) lies on the line connecting \((a_j, 0)\) and \((0, b_j)\).
There are multiple test cases. The first test case contains an integer \(T\) (about 5), indicating the number of test cases. For each test case:
The first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)), indicating the number of attacks and the number of bridges.
For the following \(n\) lines, the \(i\)-th line contains two integers \(x_i\) and \(y_i\) (\(1 \le x_i, y_i \le 10^9\)), indicating an attack.
For the following \(m\) lines, the \(j\)-th line contains two integers \(a_j\) and \(b_j\) (\(1 \le a_j, b_j \le 10^9\)), indicating a bridge.
It's guaranteed that no two bridges are the same, but DreamGrid can attack the same place for multiple times. It's also guaranteed that most of the attacks are distributed randomly and uniformly in a certain range, but the bridges may not be randomly distributed.
For each test case output \(m\) lines. The \(j\)-th line contains one integer, indicating the number of attacks the \(j\)-th bridge receives.
1 4 3 1 4 2 2 4 1 1000000000 1000000000 5 5 6 3 3 6
2 2 2
Bridge 1 receives attacks at (1, 4) and (4, 1).
Bridge 2 receives attacks at (2, 2) and (4, 1).
Bridge 3 receives attacks at (1, 4) and (2, 2).
The attack at (1000000000, 1000000000) does not influence any bridge.
Author: ZHANG, Yuan
Source: ZOJ Monthly, March 2018