Мінімізуйте максимальну відстань#12963

Мінімізуйте максимальну відстань (Розбір)

Використаємо двійковий пошук, щоб знайти відповідь. Маючи обмеження на максимальну відстань , ми можемо що наша площина розіб’ється на такі прямокутники, в кожному з яких будь-які дві сусідні точки, по горизонталі або вертикалі, мають відстань не більшу за обмеження.

Розглянемо один прямокутник і визначимо чи можна його точки розбити на потрібні нам групи по 2 та по 3. У випадку коли в прямокутнику лише 1 точка, то ми взагалі не можемо ніяк розбити на групи. Якщо кількість точок в прямокутнику парна, то ми можемо розбити на групи по 2 і в ці групи будемо ставити пари сусідніх точок.

Останнім випадком є ситуація коли кількість точок є непарною, тоді можна довести що якщо існує розбиття на групи, то існує й розбиття на такі групи що є лише одна група із 3-х точок. Ці три точки або три підряд в одному ряді, або три підряд в одному стовпці, або усі ці 3 точки знаходяться в двох сусідніх рядках та двох сусідніх стовпцях (як у малюнку для другого прикладу сині точки).

Якщо розфарбувати такий прямокутник у шаховому порядку, припустимо що кількість чорних більша за кількість білих точок. Група з 3-х точок повинна містити дві точки чорного кольору. Єдиним випадком коли це справді важливо, коли в прямокутнику або один рядок, або один стовпець. У решті випадків якщо можна вибрати хоча б якусь групу з 3-х точок, що задовольняють умову на максимальну відстань, то й можна вибрати групу з 3-х точок, що буде задовольняти одразу умову на відстань та умову на те що дві точки чорного кольору.

Враховуючи вищесказане, нам цікаво лише прямокутники із непарною кількістю елементів. Якщо у нас утвориться прямокутник 1 \times 1, то ми знаємо що така відстань є поганою. Після цього нам цікаво чи немає жодних проблем у прямокутниках 1 \times k або k \times 1. Наступним кроком ми можемо видалити ті прямокутники в яких можна вибрати групу з 3-х горизонтально або вертикально послідовних точок.

Серед тих що залишились потрібно перевірити чи є в кожному прямокутнику r_i та c_j такі що \sqrt{r_i^2 + c_j^2} \le d. Оскільки прямокутників може бути багато, знайдемо окремо \max \min r_i по рядках та \max \min c_j по стовпцях. Тоді достатньо перевірити чи \sqrt{(\max \min r_i)^2+(\max \min c_j)^2} \le d

Складність O((n + m) \cdot \log).