Автор задачи и разработчик: Даниил Орешников
Для начала перейдем в другую систему координат: работать с суммой по максимумам из двух величин неудобно. Множество точек, для которых $$$\max(|x - x_i|, |y - y_i|) = d$$$ — это квадрат со стороной $$$2d$$$ с центром в $$$(x_i, y_i)$$$. Если повернуть плоскость на $$$45^\circ$$$ и сжать координаты в $$$\sqrt{2}$$$ раз, получится «ромб» с тем же центром, но задаваемый равенством $$$|x - x_i| + |y - y_i| = d$$$. Таким образом, мы свели задачу к тому, чтобы найти такую $$$(x, y)$$$, для которой в новых координатах $$$$$$\sum\limits_{i=1}^n p_i \cdot (|x - x_i| + |y - y_i|)$$$$$$ минимальна (разумеется, сжимать координаты при этом не обязательно, можно оставить все вычисления в целых числах).
А эту сумму уже можно разбить на две независимые суммы по $$$x$$$ и по $$$y$$$, после чего выбирать $$$x$$$ и $$$y$$$ независимо. Разберем, как выбрать оптимальный $$$x$$$. Перейдем в новые координаты, сделав замену $$$x' \gets x + y$$$, $$$y' \gets x - y$$$. После чего, чтобы минимизировать $$$\sum p_i |x' - x_i'|$$$, заметим, что нам надо найти «взвешенную медиану» множества $$$x_i$$$, то есть точку, слева и справа от которой сумма $$$p_i$$$ не превосходит половины всей суммы (иначе можно сдвинуть $$$x'$$$ в сторону большей суммы $$$p_i$$$ и уменьшить искомую сумму). А это можно сделать, просто отсортировав все точки по $$$x_i'$$$ и пройдясь линейным проходом, считая сумму $$$p_i$$$.
Таким образом, найдем оптимальный $$$x'$$$, после чего тем же образом найдем оптимальный $$$y'$$$. Чтобы вернуться в исходные координаты, достаточно взять $$$x = \frac{x' + y'}{2}$$$ и $$$y' = \frac{x' - y'}{2}$$$, но для вывода даже не надо делить их на $$$2$$$. Время работы решения — $$$\mathcal{O}(n \log n)$$$.