Тема: задача на дерево отрезков
Манхэттенское расстояние
На плоскости дано N различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем
считать |x1 - x2| + |y1 - y2|. Для каждой точки требуется найти одну из ближайших к ней точек.
Формат входных данных
Первая строка входного файла содержит целое число N (1 < N <= 100000). Следующие N строк
содержат по два числа — координаты точек. Координаты — целые числа, по модулю не
превышающие 10000. Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать N целых чисел, разделенных пробелом: i-е число есть номер
одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во
входном файле, начиная с единицы.