Ctrl K

Убрать одну точку

Сложная
На плоскости дан набор точек points, где points[i] = [x, y] — целые координаты. Расстояние между точками считается «по клеткам»: между (x1, y1) и (x2, y2) оно равно |x1 − x2| + |y1 − y2|. **Размах** набора — наибольшее такое расстояние между двумя его точками. Удалите ровно одну точку так, чтобы размах оставшихся был как можно меньше, и верните этот размах. Точки могут совпадать.
Пример 1
points=[[1, 1], [2, 5], [6, 2], [20, 20]] → 7

Точка (20, 20) далеко от остальных — уберём её. Среди оставшихся самые далёкие друг от друга (2, 5) и (6, 2): |2 − 6| + |5 − 2| = 7.

Пример 2
points=[[4, 4], [4, 4], [9, 1]] → 0

Убираем (9, 1) — остаются две одинаковые точки, расстояние между ними 0.

Пример 3
points=[[1, 1], [3, 3], [5, 5], [7, 7]] → 8
Ограничения
  • 3 ≤ len(points) ≤ 10⁵
  • points[i] = [x, y], 1 ≤ x, y ≤ 10⁸
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиБлижайшая пара датчиков СложнаяПоворотная камера СложнаяПары углов без лишних соседей СложнаяЧистый прямоугольник на кнопках СложнаяСамый маленький загон Средняя
загружаем Python…
Вход
points=[[1, 1], [2, 5], [6, 2], [20, 20]]
Ожидается
7

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 155 тестов на сервере, включая скрытые.