Closest point

Revision en4, by Azret, 2015-09-28 18:08:46

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.  - 104 <  = xi, yi <  = 104

UPD Distance between points (x1, y1) and (x2, y2) is equal to |x1 - x2| + |y1 - y2|. :P

Input
4
0 0
1 1
1 0
0 1

Output
3 3 1 1


History

Revisions

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