DMOPC '16 Contest 3 P4 - Serpent's Search

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.0s
Java 7.0s
Python 7.0s
Memory limit: 64M
Java 256M
Python 256M

Problem types

After his new game idea was finally solved, jackyliao123 returns home from school and unwinds in his room for the rest of the evening. He was in the middle of downloading more Rem when his phone rang. It was his old friend, who had called to ask for advice on his side project!

In, the player is a snake who tries to survive in a world of legless reptiles. Because one dies in the event of a head-on collision with another player, jackyliao123 is tasked with implementing a component of the path-finding algorithm which actively seeks to avoid such collisions.

The current instance of time in the game contains N other players, representing the points which the player character wants to avoid. However, the player has Q instances of the game open and as a result, must update the game-state for their path-finding.

The N opposing snakes (x_i, y_i) (1 \le i \le N) and the Q queried snakes (x_j, y_j) (1 \le j \le Q) are represented by an ordered pair in the Cartesian plane.

For each of the Q queried snakes controlled by the player, jackyliao123 must determine the squared distance of the nearest point from the N opposing points d^2, and the number of those N points which have a squared distance equal to d^2.

Can you write a program to help jackyliao123 help his friend?

Input Specification

The first line of the input will contain a single integer N, denoting the number of opposing snakes to consider.

The next N lines will each contain two space-separated integers (x_i, y_i), representing the location of the i^{th} opponent.

The next line will contain a single integer Q, denoting the number of games the player is playing simultaneously.

The next Q lines will each contain two space-separated integers (x_j, y_j), representing the location of the j^{th} player character.


Subtask 1 [20%]

1 \le N, Q \le 100

0 \le x_i, y_i, x_j, y_j \le 100

Subtask 2 [80%]

1 \le N, Q \le 10^5

-10^9 \le x_i, y_i, x_j, y_j \le 10^9

Output Specification

Your program should output two space-separated integers on a single line for each of the Q queries.

The first integer d^2 represents the square of the Euclidean distance between the queried point and the closest of the N snakes.

The second integer represents the number of points from the set of N opponents whose squared distance from the queried point is equal to d^2.

Sample Input

0 0
98 0
100 0
1 0
49 0

Sample Output

1 1
2401 2


  • 9
    wleung_bvg  commented on Feb. 20, 2018, 9:24 a.m. edit 3

    Is there any possibility that test case 5 in batch 2 is incorrect? Given that none of the solutions so far have gotten 100/100, it seems a bit suspicious. Of course, my solution could just be completely wrong (and it probably is...)

    Edit: after many years, I have decided to fix the data (hopefully).