\begin{proposal}{Лампочки}{lights.in}{lights.out}{}

\Author                  
Минаев Борис

\ProblemIdea
Дано клеточное поле (размером до 5000$\times$5000). На нем расположены лампочи (в некоторых клетках). Определим "освещенность" клетки как манхэттенское расстояние до ближайшей лампочки (чем меньше~--- тем освещеннее). Необходимо добавить на поле одну лампочку так, чтобы максимальная освещенность среди всех клеток поля была минимальна.

\ProblemVariations

\SolutionIdea
Бфсом найдем освещенность каждой клетки поля. Отсортируем их подсчетом по не возростанию. Как проверить, что мы можем добавить одну лампочку так, чтобы освещенности всех были меньше либо равны $R$? Рассмотрим все клетки, текущая освещенность которых $\ge R$. Нам необходимо найти такую клетку, что ромб, с центром в некоторой клетке, с диагоналями $2R - 1$, покроет все эти клетки. Это тоже самое, что проверить, лежит ли на пересечении таких же ромбов с центрами в заданных клетках, хотя бы одна клекта (в нее поставим ласпочку). Чтобы быстро пересекать робмы будем хранить максимальные и минимальные значения среди клеток велечин $(x + y)$ и $(x - y)$. Будем перебирать ответ (яркость) от $m + n$ (стороны поля) до $0$. Каждый раз релаксируя максимумы и минимумы величин $x+y$ и $x-y$ клетками, освещенность которых равна рассматриваемой. И после этого проверяя существование клетки на пересечении ромбов. Если на некотором этапе мы не нашли такой клетки, значит, ответ~--- текущая освещенность $+ 1$.

\end{proposal}
