2015-03-10 13 views
1

Ответов на вопрос во время интервью. Нам даны N точек на двумерной плоскости x[0],y[0].......x[n-1],y[n-1] и целое число K.K-окружение Минимальная площадь Площадь

Нам нужно найти минимальную площадь квадрата с целыми координатами в виде вершин со сторонами, параллельными оси координат. охватывая по крайней мере K заданных N точек, без точки, лежащей на границе квадрата, т. е. все точки K должны быть строго внутри квадрата.

Я думал о классической минимальной проблеме прямоугольника прямоугольника, но не мог получить случай, по крайней мере, для K точек. Как подойти к этому? Заранее спасибо.

ответ

-1

Поскольку длина стороны наименьшего квадрата ограничена сверху разницей между координатой min/max x/y, мы можем использовать двоичный поиск по длине стороны. Таким образом, нам нужно только рассмотреть проблему решения: для заданной длины L проверить, существует ли квадрат со стороной L, содержащий по крайней мере K точек.

Эта проблема решения равна положению n квадратов с длиной стороны L, центрированной в каждой точке, и определяет, будет ли максимальное количество перекрытий (глубина расположения коробок). Используя метод плоской развертки, проблема решения может быть решена в O (n lg n) времени, и, следовательно, задача оптимизации может быть решена в O (n lg n lg U), где U - верхняя граница длины стороны.

Смежные вопросы