Nearest euclidean neighbor with constraint, in case of ties return the first one according to input

Revision en1, by pabloskimg, 2018-09-25 16:17:52

There are N (<= 2*10^5) 2D points with coordinates x,y and cost c. There are M (<= 2 * 10^4) queries, each query is a point (x,y) with cost c. For each query, you need to return the point with cost <= c that is closest to the query using euclidean distance. In case of ties, return the point that appears first in the input. The full problem statement can be found here: https://icpcarchive.ecs.baylor.edu/external/77/p7744.pdf.

Any ideas on how to solve it?

Tags k-nearest neighbors, constraint, #geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English pabloskimg 2018-09-26 16:00:58 89
en3 English pabloskimg 2018-09-26 03:26:12 984
en2 English pabloskimg 2018-09-25 20:07:59 1
en1 English pabloskimg 2018-09-25 16:17:52 560 Initial revision (published)