Всем привет!
Как решать следующую задачу? Даны N точек на плоскости (N <= 1000), найти минимальную площадь прямоугольника, покрывающего все эти точки. Стороны прямоугольника не обязательно должны быть параллельны осям координат. Я читал, что это можно сделать используя выпуклую оболочку, но не очень понял как.
Помогите пожалуйста, надеюсь в нынетекущих контестах таких задач нет.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 162 |
| 4 | nor | 153 |
| 5 | maroonrk | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 150 |
| 8 | atcoder_official | 145 |
| 8 | Petr | 145 |
| 10 | pajenegod | 144 |
Если у нас есть выпуклая оболочка множества, то достаточно строить прямоугольники только на отрезках этой оболочки — ориентация подходящего прямоугольника будет совпадать с ориентацией какого-то из отрезков оболочки, и одна из его сторон будет содержать этот отрезок.
При указанных ограничениях это дает несложное решение за N^2 — O(N) кандидатов и проверка каждого наивным перебором за О(N).
А быстрее можно? :)
И как доказать факт про выпуклую?
Можно и быстрее; для заданного выпуклого многоугольника покрывающий прямоугольник минимальной площади можно найти за линейное время. Аналогично поиску диаметра этого многоугольника с помощью rotating calipers, только теперь нам нужно поддерживать две взаимно перпендикулярные пары rotating calipers вместо одной. А дальше аналогично — рассматриваем критичные углы для каждой из касательных, выбираем минимальных из четырех, поворачиваем...
По поводу доказательства — никогда не интересовался доказательствами, если честно:) Подозреваю, что его можно найти в любой фундаментальной книге по геометрии, вроде Препараты/Шеймоса) Или даже доказать самостоятельно, если немного подумать)
Что-то не вижу задачи в книге Препарата и Шеймоса(
Факт не совсем верен. Верно, что оптимальный прямоугольник таков, что либо два из его углов совпадают с двумя противоположными вершинами выпуклой оболочки, либо на одной из его сторон лежит одна из сторон выпуклой оболочки.
В этом легко убедиться, если предположить, что на каждой стороне по одной точке и покрутить прямоугольник. Тогда площадь прямоугольника будет меняться, как произведение двух каких-то синусов (на константу), а произведение двух каких-то синусов — это, в свою очередь, сумма каких-то синусов/косинусов. Косинусы и синусы — выпуклые функции (в определённых рамках, конечно), значит, их сумма тоже выпукла, а значит, минимум достигается на границе интервала, то есть, когда они из сторон прямоугольника упёрлась в ещё одну вершину выпуклой оболочки.
Из первого не следует второе? Оо
Что первое, что второе?
Отвечал к первой версии правки)
два из его углов совпадают с двумя противоположными вершинами выпуклой оболочки — при этом все равно какая-то из сторон оболочки будет лежать на одной из сторон прямоугольника.
Если нет — значит, можно еще "покрутить" и уменьшать площадь (согласно рассуждениям, которые ты сам написал в следующем абзаце) до тех пор, пока не упремся в еще одну вершину, а из выпуклости оболочки следует, что мы при этом полностью накроем какую-то сторону этой оболочки.
Если два противоположных угла попали в вершины, то мы вылезем за рамки, в которых функции выпуклые.
Кстати., даже если только один угол прямоугольника попал в вершину выпуклой оболочки, то всё равно можем вылезти. Например, если рассмотреть треугольник со сторонами 1000, 1000, 1.
Что не так с этим треугольником? У меня плохо с воображением)
На всякий случай погуглил, пишут что указанного мною условия достаточно.
Да, я что-то затупил, извиняюсь.
"В этом легко убедиться, если предположить, что на каждой стороне по одной точке и покрутить прямоугольник. " — Что понимается под кручением прямоугольника? Судя по всему, это не поворот, ведь предполагается, что его площадь будет изменяться.
Да, имеется в виду поворот всех прямых содержащих стороны прямоугольника, относительно вершины выпуклой оболочки, через которую она (сторона) проходит. Четыре новые прямые по-прежнему образуют прямоугольник, поскольку это по-прежнему две пары параллельных прямых, перпендикулярных друг другу (в смысле, прямые из разных пар перпендикулярны друг другу).
Хорошо, тогда что понимается как "произведение 2 синусов"?
если рассмотреть отрезок (пусть его длина
l) между двумя противоположными вершинами, в которые упираются стороны, то ширина полосы, в которую он влезает равна l·sin(α), где α — угол наклона между прямыми и этим отрезком. Так же и с другим аналогичным отрезком. Ну а площадь прямоугольника — произведение двух этих ширин. При этом угол наклона к прямым у двух отрезков отличается на некую константу.Ага, теперь понятно. Только вот там дальше не все так просто. "Косинусы и синусы — выпуклые функции (в определённых рамках, конечно), значит, их сумма тоже выпукла, а значит, минимум достигается на границе интервала," — не факт, что рамки, в которых сумма синусов и косинусов выпукла, содержат в себе границы, в которых можно менять угол α, и нет гарантии, что минимум действительно достигается на экстремальном значении α
Если угол между этими отрезками составляет
, α, то (опустив константу) получаем, что 
. cos(x) — константа, α меняется в промежутке [L, R], где 0 ≤ L ≤ R ≤ π. При этом 
. Таким образом, функция - cos рассматривается только на промежутке 
. Чтобы функция была на этом отрезке выпукла, надо немного получше ограничить α...
То-то и оно(