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

Revision ru4, by Azret, 2015-09-28 18:07:57

Всем привет!

Сразу перейду к задаче — дано множество из N (1 < N <  = 105) различных точек с целочисленными координатами на координатной плоскости. Для каждой точки надо найти номер ближайшей к ней точки (из множества, кроме неё самой). Если таких несколько нужно вывести точку с минимальным номером.  - 104 <  = xi, yi <  = 104

UPD Расстояние между точками (x1, y1) и (x2, y2) равно |x1 — x2| + |y1 — y2|. :P

Input
4
0 0
1 1
1 0
0 1

Output
3 3 1 1
Tags ближайшая точка, точки, hard, сложно

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 Первая редакция (опубликовано)