Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

The Archipelago of Mirpur

By Zeronfinity · Limits 1s, 512 MB

The archipelago of Mirpur consists of N islands. The famous architect PogPog was hired to connect all these islands by creating bi-directional bridges among them. PogPog can create a bridge only when the Euclidean distance between two islands is less than or equal to K. For each pair of islands; if their distance is less than or equal to K, PogPog will definitely connect them through a bridge.

In this problem, each island is represented by a point with 2-dimensional coordinate system. Moreover, the coordinates of two different islands can be the same too! Suppose, the coordinate of one island is (X1, Y1) and the coordinate of another island is (X2, Y2). The Euclidean distance between them is defined as:

$ {({(X_1 - X_2)}^2 + {(Y_1 - Y_2)}^2)}^{0.5} $

In the archipelago, a group of islands connected together is called a kingdom. If it’s possible to travel to an island from another island through a bridge or sequence of bridges, the islands are considered to be in the same kingdom. Similarly, if there is no way to travel to an island from another island, the islands are in different kingdoms.

You will be given some queries, each containing an integer M. For each query, you have to tell the minimum value of K such that Mirpur Archipelago contains at most M kingdoms.

Input

Input starts with an integer N (1 ≤ N ≤ 1000), the number of islands. The following N lines describe the coordinates of the islands. Each line contains two space-separated integers X and Y (0 ≤ X, Y ≤ 1000), the coordinate of an island.

Then, an integer Q (1 ≤ Q ≤ 1000) is given, the number of queries. Each of the following Q lines contains an integer M (1 ≤ M ≤ N), the number of kingdoms for which you have to find the answer as described in the problem statement.

Output

For each query, print the minimum value of K in a single line. Your answer will be considered correct if the absolute error between your answer and the correct answer is less than or equal to 10-6.

In this problem, consider that K can never be negative i.e. the minimum possible value for K is 0.

Sample

InputOutput
3
3 4
0 0
11 10
3
3
2
1
0.000000000
5.000000000
10.000000000

When K = 0, PogPog can not connect any of the islands, so the number of kingdoms are 3. In other words, the minimum value of K that satisfies M = 3 is K = 0. When M = 2, the minimum value of K = 5 as island no 1 and island no 2 are connected then. Thus the number of kingdoms is 2, one kingdom consists of the islands 1 and 2 while the other kingdom consists of island 3 only. Similarly, the minimum value of K for M = 1 is 10 as island 1 and island 3 become connected then and thus the number of kingdoms is 1.



Discussion
Statistics

72% Solution Ratio

dip_BRUREarliest, 3w ago

dip_BRURFastest, 0.1s

Annabelle_Lightest, 6.2 MB

Taran106Shortest, 1188B

Submit

Login to submit