I wonder if somebody can help me to solve this problem: There is a set X of N point on the plane not **two** sharing the same x-coordinate, and a set Y of S points. The task is to compute for each point on X the distance to its closest point on Y with a precision of 10^-2 N,S<=10^5 and the coordinates of the points x,y <=10^6

**UPD:** Sorry for my English I corrected a mistake in the first line

http://en.wikipedia.org/wiki/Delaunay_triangulation NLogN with any precision

You can use the following heuristics: choose a random line and project all points on it. Then, for each point X, move two pointers in the both directions and stop a one when |

pos_{X}-pos_{Y}| > =Ans, where the expression under modulo is distance between projections ofXand some current pointYandAnsis the best answer for theXat this moment.This algo is easy to implement and it works good in average, but fails on a special test cases (something like 'a lot of points on a circle'). I've heard that it works in in the 'find two nearest points' problem.

You can also take a look at the Codechef's CLOSEST problem and its editorial.

The test is: X = points on the large circle (coordinates are rounded to integers), Y = points near the center of the circle

It's true even for more complicated problem, in case X = Y (for each point from X find the nearest one from Y).