Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Вариант 24.09.04 13:47 Число просмотров: 1658
Автор: leo <Леонид Юрьев> Статус: Elderman Отредактировано 24.09.04 17:45 Количество правок: 2
|
Интуитивно кажется, что если многоугольник выпуклый, то максимальная площадь прямоугольника будет если как минимум две его вершины лежат на гранях многоугольника. Но по-хорошему это нужно доказать.
Когда две вершины лежат на гранях, то явно задаётся либо одна из сторон, либо диагональ прямоугольника.
Цикл перебора - «первой» вершиной прямоугольника по граням многоугольника, вложенный цикл - в качестве «второй» вершины выбираем одну из трех оставшихся, еще один вложенный цикл - выбранной «второй» вершиной прямоугольника снова по всем граням многоугольника.
Внутри циклов выбираем максимальный прямоугольник, у которого две заданные вершины лежат на двух заданных гранях многоугольника. Эта подзадача решается аналитически. Грани, на которых лежат вершины, разбиваются на секторы в точках, которые соответствуют «перескакиванием» пересечений прямых в продолжение сторон прямоугольника с гранями многоугольника, для каждого сектора ищется максимум площади (уравнение на локальный максимум функции)...
При заданном минимуме по высоте и ширине (соответственно площади) многие циклы поиска можно быстро отбрасывать. Сложность задачи между O*N*N и O*N*N*N, где N-количество граней многоугольника.
Если многоугольник не выпуклый, то для начала по-моему можно поступать также, просто отбрасывая варианты когда стороны прямоугольника пересекаются с «вогнутыми» гранями многоугольником.
Удачи!
|
|
|