http://acm.timus.ru/problem.aspx?space=1&num=1369
today I have solved problem ural 1369. which spent me nearly two months and 600+ submits. now I'll share you approach of this problem:
first find voronoi diagram of this problem, and using sweepline algorithm to scan x cooridinates voronoi convex polygon
using set to record the point inside the polygon(sort by y cooridinates), for query, find the nearest y cooridinates scan the set from this nearest y points, if dist>min_dist+eps break..
I use this approach and WA on test 17, it is because there is precision error on voronoi points.
then I change sweepline the y cooridinates,and sort the set by x, it got WA on test 21(a different test)
so I combine this two approach together, and compare the two results,choose the minimum distance,finally get AC..