749. The Doctor and the Zygons
0
Easy
The Doctor is engaged in a battle against the Zygons once again. This time, he is equipped with a special device that can eliminate all Zygons within its range. However, the range of the device keeps changing. Assist the Doctor in determining the number of Zygons he can eliminate.
Assume that the Doctor is positioned at the center of a circle. Given N points on the coordinate plane, where the ith point is located at coordinates (x_i, y_i) representing the position of the ith Zygon, you need to answer Q queries.
In each query, you will be provided with an integer r_i, indicating the range of the Doctor's special device. Considering that you draw a circle centered at the origin (0,0) with a radius of r_i, you need to report the number of Zygons that the Doctor will be able to eliminate, i.e., the points lying inside or on the circumference of this circle.
Print the answer for each query on a new line.
Input Format
The first line contains a single integer N, indicating the number of points on the coordinate plane.
Each of the next N lines contains 2 space-separated integers x_i and y_i, representing the x and y coordinates of the ith point.
The next line contains a single integer Q, indicating the number of queries. Each of the next Q lines contains a single integer, where the integer on the ith line represents the parameter of the ith query r_i.
Output Format
For each query, print the answer on a new line.
Example
Input
5
1 1
2 2
3 3
-1 -1
4 4
2
3
32
Output
3
5
Constraints
1 <= N <= 10^5
-10^9 <= x_i, y_i <= 10^9
1 <= Q <= 10^5
1 <= r_i <= 10^18
Loading...
View Submissions
Console