side), (side, 0) и (side, side). На ограде участка размечены места для камер: spots[i] = [x, y] — координаты места, все места различны и лежат на границе квадрата.
Нужно выбрать ровно cameras мест и поставить туда камеры так, чтобы они стояли как можно дальше друг от друга. Расстояние между точками (x₁, y₁) и (x₂, y₂) считается как |x₁ - x₂| + |y₁ - y₂| (манхэттенское).
Верните наибольшее возможное значение минимального расстояния между двумя выбранными камерами.side=3, spots=[[0, 0], [0, 3], [3, 3], [3, 0], [1, 0], [3, 2]], cameras=4 → 3
Ставим камеры в четыре угла: любые две из них отстоят друг от друга хотя бы на 3.
side=2, spots=[[0, 1], [1, 2], [2, 1], [1, 0], [0, 0]], cameras=5 → 1
Ставим все пять камер; ближе всех друг к другу (0, 1) и (0, 0) — расстояние 1.
side=4, spots=[[0, 2], [2, 4], [4, 2], [2, 0], [0, 0], [4, 4]], cameras=4 → 4
side ≤ 10⁹len(spots) ≤ min(4 · side, 15 000)spots[i] лежит на границе квадрата, все точки различныcameras ≤ min(25, len(spots))side=3, spots=[[0, 0], [0, 3], [3, 3], [3, 0], [1, 0], [3, 2]], cameras=4
3
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 38 тестов на сервере, включая скрытые.