задача на дерево отрезков

Для каждой точки найдем ближайшую к ней которая лежит левее ее либо имеет ту же икс координату, но лежит ниже. Очевидно что дальше для каждой точки легко найти ближайшую среди всех остальных.
Отсортируем точки лексикографически (т.е. по икс координате, а при равных иксах по игрекам). Пусть на i-м шагу мы рассматриваем точку с координатами (x,y). Найдем для нее ближайшую точку (x',y').
|x-x'|+|y-y'| - минимально
x>=x', поэтому первый модуль можно убрать
x-x'+|y-y'| - минимально

Теперь рассмотрим 2 случая:

1) y'<=y
Тогда второй модуль раскроется со знаком + и получим
x-x'+y-y'=(x+y)-(x'+y') - минимально
Значит, нам нужно максимизировать (x'+y').
Заведем дерево отрезков по игрекам, где для каждого игрека будем хранить максимальное значение (x'+y') среди точек с таким игреком, которые мы уже добавили в дерево. Тогда чтобы максимизировать (x'+y') надо просто найти максимум среди точек с игреками [-10000,y].

2) y'>y
Второй модуль раскроется со знаком минус. Тогда имеем:
x-x'+y'-y=(x-y)-(x'-y') - минимально
Опять таки, нам нужно максимизировать (x'-y'). Заведем второе дерево отрезков и будем хранить в нем величины (x'-y'). Отвечать на запросы будем так же как и в первом случае.

Теперь просто из двух найденных точек выберем ту, которая ближе. Далее обновим оба дерева отрезков (добавим текущую точку) и перейдем к следующей. Сложность O(NlogR+NlogN), где R - макс. y координата. Если бы координаты могли быть большими, то имело бы смысл сделать сжатие координат и тогда сложность была бы просто O(NlogN).

Почему не получится? Можно строить дерево отрезков по сжатым координатам, а минимум брать по старым.

Казалось бы, можно просто перебрать, с каким знаком раскроется каждый модуль в манхеттенской метрике, и при каждом варианте (их 4) отсортировать все точки по этому критерию, и попроверять две соседние. Т.е. 4 сортировки и прохода.

Ну один из четырёх:
x+y, -x+y, x-y, -x-y.
Понятно, что для любой точки ближайшая к ней будет и ближайшей в одной из этих четырёх сортировок.

Действительно, берём метрику:
|x1-x2|+|y1-y2| -> min
И пусть модули оба с плюсом раскрылись. Тогда:
x1-x2+y1-y2 = (x1+y1)-(x2+y2) -> min
Это значит, что при таком раскрытии модуля точки 1 и 2 будут соседними в порядке сортировки по x+y.
Повторяя эти рассуждения для 3 других способов раскрытия модулей, как раз и получаем моё утверждение.

Рассмотрим, например, тест:
4
4 0
7 6
3 6
1 5

Тут всего 4 точки. Ближайшей точкой к (4,0) будет точка (3,6) с расстоянием до нее 7.
Теперь переберем 4 случая раскрытия модуля, отсортируем массивы и посмотрим, будет ли хоть в одном из них точка (3,6) соседней с (4,0):

1) x+y: (4,0), (1,5), (3,6), (7,6).
2) x-y: (1,5), (3,6), (7,6), (4,0).
3) -x+y: (4,0), (7,6), (3,6), (1,5).
4) -x-y: (7,6), (3,6), (1,5), (4,0).

Как видно, ни разу точки (4,0) и (3,6) не оказываются рядом. Кстати, варианты 3-4 сортировки это просто развернутые задом наперед варианты 1-2.