Поиск подмножества на плоскости с минимальным диаметром

[trozki_187]

mihaild в сообщении #1605889 писал(а):

Да, правильно.
Нет, их $O(l^2)$. Диагональ имеет длину $O(l)$, а квадрат задается двумя точками из неё.

Если кратко: Завести переменную для индекса нижнего угла. Пройтись циклом по индексу верхнего угла. В цикле инкрементировать нижний указатель до тех пор пока больше чем $K$ точек. Запоминать минимальную сторону. Наверное, как то так.

Почему, достаточно рассмотреть квадраты на диагонали?

[mihaild]

Да, правильно. Это стандартный прием, называется "метод двух указателей".

trozki_187 в сообщении #1605900 писал(а):

Почему, достаточно рассмотреть квадраты на диагонали?

Недостаточно, но каждый квадрат лежит на какой-то диагонали ($x - y = \operatorname{const}$).

[trozki_187]

mihaild в сообщении #1605905 писал(а):

Недостаточно, но каждый квадрат лежит на какой-то диагонали ($x - y = \operatorname{const}$).

Да, уже сообразил про побочные диагонали. Большое спасибо!