TSS Club Fair 2017 Problem B

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

There's a crisis in Hawaii! The great volcano "Mauna Loa" is about to erupt! The Mauna Loa is located in the middle of the largest island in Hawaii, with almost 200\,000 people living nearby.

As a responsible dictator, Joey quickly pulled out a map containing the locations of all N houses on the island. He came up with Q different scenarios on how the volcano might explode. Each scenario will describe the range of the volcano. Any house within the range of the volcano will be instantly destroyed. Please find how many houses will be destroyed in each of the scenarios.

Input Specification

The first line will contain N, Q, denoting the number of houses and the number of scenarios respectively.

The next N lines will contain 2 integers x, y denoting the position of the house relative to the volcano measured in meters.

The next Q lines will contain a single integer r, denoting a scenario where all houses within r meters of the volcano will get destroyed.

Output Specification

For each scenario, print a single integer on a line, denoting the number of houses that will be destroyed in that scenario.


N \le 186\,738

Q \le 200\,000

-1\,000\,000 \le x, y \le 1\,000\,000

0 \le r \le 1\,414\,214

At least 50\% of the test cases will have N, Q \le 1\,000.

Sample Input 1

4 3
2 2
-4 0
0 -5
5 -5

Sample Output 1


Sample Explanation 1

The island's houses are distributed roughly as described in the image. The 3 rings describe the ranges of the volcano in each range.

In the scenario with the smallest eruption, no houses are destroyed.

In the scenario with the medium eruption, 2 houses are destroyed.

In the scenario with the largest eruption, 3 houses are destroyed.


You may want to use fast I/O in your program.


There are no comments at the moment.