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

Правка ru5, от Azret, 2015-09-28 18:09:09

Всем привет!

Сразу перейду к задаче — дано множество из 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
Теги ближайшая точка, точки, hard, сложно

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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 Первая редакция (опубликовано)