Random geometric graphs P34324

Professor J. ‍Díaz is interested in random geometric graphs. To construct a random geometric graph G(n,r) with n vertices and radius r, Prof. ‍Díaz proceeds as follows. First, he chooses n points V={v₁,…,v_n} uniformly distributed at random in the unit square [0,1]². These points correspond to the vertices of the graph. Then, he joins with an edge any pair of points whose Euclidean distance is at most r. The following figures illustrate three such random geometric graphs.

‍	‍  ‍	‍
n=100, r=0.12	n=100, r=0.15	n=100, r=0.20

It is not difficult to see that the expected number of edges in a random geometric graph G(n,r) tends to π r² n for large n. Moreover, recent theoretical results show that random geometric graphs exhibit a threshold phenomenon regarding their connectivity: When r is slightly larger than Θ(√logn/n ), such graphs tend to have just one connected component, whereas when r is slightly smaller than this value, graphs tend to have many connected components. (In this problem, logn denotes the natural logarithm of n.)

Let r(c,n) =√clogn/n. In order to help Prof. ‍Díaz to better understand this threshold behavior, please write an efficient program to determine whether a random geometric graph G(n,r(c,n)) is connected or not, given the n coordinates of its vertices and the value c.

Input

Input consists of several cases. Every case begins with n and c, followed by n real numbers: the x-coordinates of the vertices. Follow n real numbers: the y-coordinates of the vertices in the same order. Assume 2 ≤ n ≤ 2 · 10⁴, 0 < c < 2, and that all coordinates were uniformly generated at random between 0 and 1. The input cases have no precision issues.

Output

For every case, tell if the given random geometric graph G(n,r(c,n)) is connected or not.