Trick or Treat!

Авторы задачи: Захар Черемных и Даниил Орешников, разработчик: Даниил Орешников

При рассмотрении точки отдельно рассмотрим ближайшие к ней слева-сверху, слева-снизу, справа-сверху и справа-снизу. Такое разделение позволяет перейти к формуле расстояния без модулей.

Будем обрабатывать точки слева направо сканирующей прямой. В таком случае от точки $$$(x_i, y_i)$$$ расстояние до точек $$$(x_j, y_j)$$$ слева-сверху будет равно $$$(x_i - x_j) + (y_j - y_i) = (x_i - y_i) - (x_j - y_i)$$$. Для фиксированного $$$i$$$ кратчайшее расстояние достигается при максимальном $$$x_j + y_j$$$. Симметрично, для точек слева-снизу кратчайшее расстояние можно будет посчитать как $$$(x_i + y_i) - \max(x_j + y_j)$$$. Обозначим $$$d_1(A) = A_x + A_y$$$ и $$$d_2(A) = A_x - A_y$$$.

Будем хранить на сканирующей прямой все встреченные до этого точки в декартовом дереве по явному ключу по координате $$$Y$$$. Тогда при рассмотрении очередной точки $$$(x_i, y_i)$$$ будет достаточно разбить все точки на сканирующей прямой на нижнюю и верхнюю часть с помощью $$$\mathtt{split}(y_i)$$$, после чего найти $$$\max d_1$$$ в нижней части и $$$\max d_2$$$ в верхней. Для этого можно просто поддерживать максимальные значения $$$d_1$$$ и $$$d_2$$$ в каждой вершине дерева.

Осталось только рассмотреть точки строго на той же вертикали и находящиеся справа от текущей. Точки, находящиеся справа, можно, рассмотрев симметричную картину (заменив все $$$(x_i, y_i)$$$ на $$$(\mathtt{X\_MAX} - x_i, y_i)$$$) и запустив еще раз ту же самую сканирующую прямую. Рассмотреть точки с той же $$$X$$$-координатой, что и у текущей, можно за $$$\mathcal{O}(1)$$$, так как после сортировки точек как пар, ближайшие по $$$Y$$$-координате с той же $$$X$$$-координатой будут соседними с текущей.