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

Правка en2, от pabloskimg, 2018-09-25 20:07:59

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?

Теги k-nearest neighbors, constraint, #geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский pabloskimg 2018-09-26 16:00:58 89
en3 Английский pabloskimg 2018-09-26 03:26:12 984
en2 Английский pabloskimg 2018-09-25 20:07:59 1
en1 Английский pabloskimg 2018-09-25 16:17:52 560 Initial revision (published)