AS4: Многоугольник максимальной площади.

[Andrey Yu. Sobolev]

Приветствую вас, многоуважаемые пузляры!

Около года назад в НГУ проводилась олимпиада по программированию.
Одна задача кажется мне интересной. Авторство принадлежит не мне - я не
знаю, кому оно принадлежит. Однако так как задачи эти были уже
представлены публике (как бы о-публикованы?), я думаю, можно дать
возможность подумать над ними и вам...

==-AS4-========
Вход:
N - число ребер многоугольника (для простоты программирования N < 100)
L[i], i=1..N - длины ребер.
Выход:
S - максимальная площадь N-угольника с ребрами длинной L[i], _возможно,
расположенных в другом порядке_. Или -1, если такого многоугольника
не существует.
В качестве дополнительной подзадачи предлагалось нарисовать этот
многоугольник.
==-AS4-========

Разумеется, программу писать не обязательно. Тогда вопросы зададим
по-другому:
1. Стоит ли переупорядочивать ребра, и если да, то как?
2. Подсчитать макс. площадь при заданном порядке ребер.

Может, я неправильно разбил на подзадачи?

Andrey Sobolev
email: ASob...@Lords.com
______________________________________________________________________

[Allex]

Привет.

Andrey Yu. Sobolev

>==-AS4-========
>Вход:
> N - число ребер многоугольника (для простоты программирования N < 100)
> L[i], i=1..N - длины ребер.
>Выход:
> S - максимальная площадь N-угольника с ребрами длинной L[i], _возможно,
>расположенных в другом порядке_. Или -1, если такого многоугольника
>не существует.
> В качестве дополнительной подзадачи предлагалось нарисовать этот
>многоугольник.
>==-AS4-========
>
>Разумеется, программу писать не обязательно. Тогда вопросы зададим
>по-другому:
> 1. Стоит ли переупорядочивать ребра, и если да, то как?
> 2. Подсчитать макс. площадь при заданном порядке ребер.
>
>Может, я неправильно разбил на подзадачи?

9

8

7

6

5

4

3

2

1

По поводу первой подзадачи:

Лемма. Многоугольник максимальной площади с заданными сторонами выпуклый.
Доказывать?

Утверждение: Максимальная площадь не зависит от порядка сторон.
Доказательство: Докажем, что для данной площади можно получить
многоугольник с произвольным порядком сторон.
Достаточно доказать для многоугольников, у которых две стороны
поменялись местами. Соединив соответствующие концы этих сторон получим
трапецию, которую можно "зеркально отразить" относительно прямой,
перпендикулярной основаниям. В результате получим многоугольник,
в котором стороны поменялись местами.
Как известно, любая перестановка может быть получена через
композицию транспозиций, следовательно, всё.

Второй пункт. Плохо я в школе физику учил - понимаю, что надо "накачивать"
многоугольник, до тех пор, пока "давление" не сделает его площадь максимальной.
А вот реализовать это - слабо.

С уважением,
Алексей.

Alexey Demakov
e-mail: dem...@kazbek.ispras.ru
www: http://marlboro.ispras.ru:8080
ICQ: 740187

[Andrey Yu. Sobolev]

Привет!

Что-то не очень покатила задачка :( А жаль. Но все же... Она еще
не решена. Помогите, пузляры!

> >==-AS4-========
> >Вход:
> > N - число ребер многоугольника (для простоты программирования N < 100)
> > L[i], i=1..N - длины ребер.
> >Выход:
> > S - максимальная площадь N-угольника с ребрами длинной L[i], _возможно,
> >расположенных в другом порядке_. Или -1, если такого многоугольника
> >не существует.
> > В качестве дополнительной подзадачи предлагалось нарисовать этот
> >многоугольник.
> >==-AS4-========
> >
> >Разумеется, программу писать не обязательно. Тогда вопросы зададим
> >по-другому:
> > 1. Стоит ли переупорядочивать ребра, и если да, то как?
> > 2. Подсчитать макс. площадь при заданном порядке ребер.

Вот что пишет Alexey Demakov:

> Утверждение: Максимальная площадь не зависит от порядка сторон.
> Доказательство: Докажем, что для данной площади можно получить
> многоугольник с произвольным порядком сторон.
> Достаточно доказать для многоугольников, у которых две стороны
> поменялись местами. Соединив соответствующие концы этих сторон получим
> трапецию, которую можно "зеркально отразить" относительно прямой,

^^^^^^^^^^^^^^ ^^^^^^^

> перпендикулярной основаниям. В результате получим многоугольник,

^^^^^^^^^^^^^^^^^^^^^^^^^^^^

> в котором стороны поменялись местами.

Честно говоря, я не понял, где же тут трапеция. Трапеция - это
когда две стороны параллельны, так? Ну и где? То есть с чего бы это они
здесь параллельны? Или я чего-то не понял?

> Второй пункт. Плохо я в школе физику учил - понимаю, что надо "накачивать"
> многоугольник, до тех пор, пока "давление" не сделает его площадь максимальной.
> А вот реализовать это - слабо.

Ну да, это первое, что приходит в голову. Однако как это
реализовывать? Скажем, дано сто отрезков. Что будем двигать? Я забыл
упомянуть - на эти задачи было поставлено формальное ограничение по
времени, что-то типа минуты (на i386).
По-моему, идея получше: взять окружность и начать выкладывать
хорды. Если не влезло или не хватило - меняем радиус (вроде дихотомии).
Впрочем, и здесь не без проблем - скажем, лучше начинать не с самой
большой стороны - иначе может и не построиться... А будет ли площадь
максимальной?

Остается надеятся, что придет KK, Pertsel, AGu или еще кто-то и
вмиг закроют вопрос... :)

Andrey Sobolev
_____________________________________________________________________

[Prof. S.M.School]

Здравствуйте!

Возьмем две смежные стороны многоугольника и соединим их концы диагональю.
Теперь отразим нашу пару сторон относительно серединного перпендикуляра к
этой диагонали, а остальные стороны многоугольника оставим на месте. Концы
диагонали, общая вершина двух наших сторон и точка, симметричная этой вершине
относительно серединного перпендикуляра к диагонали - вершины трапеции (или
треугольника, если взятые нами смежные стороны равны). Поэтому при указанном
преобразовании сторон площадь многоугольника не изменится. При этом
многоугольник останется выпуклым (иначе площадь не максимальна), а порядок,
в котором идут две взятые нами стороны, изменится на противоположный при
сохранении порядка остальных сторон. Такими транспозициями можно добиться,
чтобы стороны шли в любом наперед заданном порядке.

>
> > Второй пункт. Плохо я в школе физику учил - понимаю, что надо "накачивать"
> > многоугольник, до тех пор, пока "давление" не сделает его площадь максимальной.
> > А вот реализовать это - слабо.
>
> Ну да, это первое, что приходит в голову. Однако как это
> реализовывать? Скажем, дано сто отрезков. Что будем двигать? Я забыл
> упомянуть - на эти задачи было поставлено формальное ограничение по
> времени, что-то типа минуты (на i386).
> По-моему, идея получше: взять окружность и начать выкладывать
> хорды. Если не влезло или не хватило - меняем радиус (вроде дихотомии).
> Впрочем, и здесь не без проблем - скажем, лучше начинать не с самой
> большой стороны - иначе может и не построиться... А будет ли площадь
> максимальной?

Это классический факт: площадь многоугольника с данными длинами сторон
максимальна, когда многоугольник - вписанный. Он называется теоремой
Крамера. Доказательство есть, например, в 11 книги А.А.Крыжановского
"Изопериметры" (М.: Физматгиз, 1959).

>
>
> Остается надеятся, что придет KK, Pertsel, AGu или еще кто-то и
> вмиг закроют вопрос... :)

:)))

Prof. Summer M. Scholl & И.Рубанов.

[Allex]

Привет.

Prof. S.M.School
>Andrey Yu. Sobolev

;-))) Про две соседние стороны - это была моя отправная точка.
А потом нашло затмение и я подумал, что две произвольные
тоже можно сразу менять. ;-)
Спасибо Prof. Summer M. School - нашёл трапецию ;-)

>> > Второй пункт. Плохо я в школе физику учил - понимаю, что надо "накачивать"
>> > многоугольник, до тех пор, пока "давление" не сделает его площадь максимальной.
>> > А вот реализовать это - слабо.
>>
>> Ну да, это первое, что приходит в голову. Однако как это
>> реализовывать? Скажем, дано сто отрезков. Что будем двигать? Я забыл
>> упомянуть - на эти задачи было поставлено формальное ограничение по
>> времени, что-то типа минуты (на i386).
>> По-моему, идея получше: взять окружность и начать выкладывать
>> хорды. Если не влезло или не хватило - меняем радиус (вроде дихотомии).
>> Впрочем, и здесь не без проблем - скажем, лучше начинать не с самой
>> большой стороны - иначе может и не построиться... А будет ли площадь
>> максимальной?
>
>Это классический факт: площадь многоугольника с данными длинами сторон
>максимальна, когда многоугольник - вписанный. Он называется теоремой
>Крамера. Доказательство есть, например, в 11 книги А.А.Крыжановского
>"Изопериметры" (М.: Физматгиз, 1959).

Следовательно, приближённое решение, по-видимому, можно так найти,
а вот точное... То бишь, формулу ;-)

>>
>>
>> Остается надеятся, что придет KK, Pertsel, AGu или еще кто-то и
>> вмиг закроют вопрос... :)

Хм, задачка-то не из лёгких, если только написано где-нибудь...

>:)))
>
>Prof. Summer M. Scholl & И.Рубанов.

С уважением,