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*_{1},…,*v*_{n}}
uniformly distributed at random in the unit square [0,1]^{2}.
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*^{2} *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 Θ(√log*n*/*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, log*n* denotes the natural logarithm of *n*.)

Let *r*(*c*,*n*) =√*c*log*n*/*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^{4}, 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.

Public test cases

**Input**

4 0.8 0.41 0.2 0.97 0.47 0.45 0.05 0.33 0.28 8 0.3 0.549918 0.669204 0.782035 0.715593 0.606206 0.126883 0.290046 0.357151 0.17341 0.910579 0.350634 0.757528 0.309185 0.690387 0.25063 0.818279

**Output**

YES NO

Information

- Author
- Jordi Petit
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Segon Concurs de Programació de la UPC - Segona Semifinal
- Date
- 2004-09-15