Ближайшая точка

Revision en1, by Azret, 2015-09-28 17:38:29

Hi all!

Straightly to the problem — you are given a set of N (1 < N <  = 105) distinct points with integer coordinates on coordinate plane. For each point you need to find number of closest point to it (from set, expect itself). If there are more than one output point with minimum number.

Input
4
0 0
1 1
1 0
0 1

Output
3 3 1 1
Tags hard, closest point

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian Azret 2015-09-28 18:09:09 22
en4 English Azret 2015-09-28 18:08:46 101
ru4 Russian Azret 2015-09-28 18:07:57 100
en3 English Azret 2015-09-28 17:41:20 26
en2 English Azret 2015-09-28 17:40:49 28 Tiny change: 'um number.\n\n~~~~~\' -> 'um number. $-10^4 <= x_i, y_i <= 10^4$\n\n~~~~~\'
ru3 Russian Azret 2015-09-28 17:40:37 28 Мелкая правка: 'м номером.\n\n~~~~~\' -= x_i, y_i
ru2 Russian Azret 2015-09-28 17:39:11 32 Мелкая правка: ' ней точки. Если так' -> ' ней точки (из множества, кроме неё самой). Если так'
en1 English Azret 2015-09-28 17:38:29 385 Initial revision for English translation
ru1 Russian Azret 2015-09-28 17:33:42 364 Первая редакция (опубликовано)