Командный чемпионат мира по программированию. Задача G

[Pavlovsky]

Прошел очередной командный чемпионат мира по программированию. Наши заняли четвертое место.
http://cm.baylor.edu/scoreboard/

Из списка задач заинтеросавала задача G. Если бы наши ее решили были бы первыми.
http://cm.baylor.edu/digital/icpc2011.pdf

Краткое описание задачи G.
Дано: длины сторон некего многоугольника. S1,S2,...,Sn.
Надо: Вычислить максимальную площадь многоугольника, который можно построить из этих длин сторон.

Пытаюсь ее решить. Возникло несколько математических проблем.

Гипотеза. Многоугольник максимальной площади должен быть вписан в некоторую окружность.

Верна ли эта гипотеза?
Если верна, то возникает вторая проблема вычислить радиус этой окружности.

[age]

Pavlovsky в сообщении #452989 писал(а):

Гипотеза. Многоугольник максимальной площади должен быть вписан в некоторую окружность.

Верна ли эта гипотеза?

Нет. Возьмите 4 стороны по 10 и 2 стороны по 1.

[Pavlovsky]

И что в этом примере не так? Получится многоугольник очень близкий к квадрату 10х10.

[TOTAL]

Pavlovsky в сообщении #452989 писал(а):

Надо: Вычислить максимальную площадь многоугольника, который можно построить из этих длин сторон.

Не это надо вычислить.

[sup]

Гипотеза верна. Порядок сторон - не важен. Радиус окружности от этого не меняется (а вместе с ним и площадь многоугольника).
Доказательство. Используем изопериметрическую задачу.

(Доказательство)

Пусть многоугольник вписан в окружность. Приклеим к его сторонам соответствующие сегменты этой окружности. Рассмотрим какой нибудь другой многоугольник с этими же сторонами с этими же сегментами. Получим фигуру с периметром исходной окружности. Площади сегментов - те же самые. Значит площадь "нового" многоугольника не больше площади исходного.

Нахождение радиуса - скучная задача с синусами. На компьютере решается без проблем.

[Equinoxe]

sup, кстати, радиус вроде можно простым бинпоиском найти

[sup]

Ну конечно. А еще и метод Ньютона существует.

[Pavlovsky]

Sup ты гений. На подобных соревнованях обычно берут в команду двух программистов и одного математика. Наш математик явно подкачал.
Пытаюсь решить скучную задачу с синусами. Получилось так:
\sum_{i=1}^{n}{\arcsin(\frac {S_i} {2R})}=\pi

Если arcsin разложить в ряд тэйлора (взять два первых члена), то получится кубическое уранение. Но вот хватит ли только двух членов? По условиям задачи точность должна быть 10^-4

-- Чт июн 02, 2011 16:49:36 --

Equinoxe в сообщении #453001 писал(а):

радиус вроде можно простым бинпоиском найти

sup в сообщении #453005 писал(а):

А еще и метод Ньютона существует

Не знаю какой лимит времени был у этой задачи. Боюсь что приближенные алгоритмы вычисления могут в этот лимит не войти.

[age]

Это как раз что-то вроде симплекс-метода. Геометрическая интерпретация симплекс-метода и есть поиск многоугольника максимальной площади. Только немножко надо модернизировать.

[TOTAL]

Pavlovsky в сообщении #453007 писал(а):

Пытаюсь решить скучную задачу с синусами. Получилось так:
\sum_{i=1}^{n}{\arcsin(\frac {S_i} {2R})}=\pi

Неверная формула. Справа не обязательно $\pi$

[Pavlovsky]

TOTAL в сообщении #453012 писал(а):

Неверная формула. Справа не обязательно

Ах да вспомнил. Центр окружности не обязательно может находиться внутри многоугольника.

[age]

Pavlovsky в сообщении #452996 писал(а):

И что в этом примере не так? Получится многоугольник очень близкий к квадрату 10х10.

Очевидно, но в одной из вершин там будет такая загагулинка из сторонок по $1$. Её вы не впишите ни в одну окружность, т.к. многоугольник будет невыпуклый.

[Pavlovsky]

age в сообщении #453018 писал(а):

Очевидно, но в одной из вершин там будет такая загагулинка из сторонок по . Её вы не впишите ни в одну окружность, т.к. многоугольник будет невыпуклый.

Вы очень ошибаетесь. Легко доказать что многоугольник с максимальной площадью - выпуклый.

[age]

Хотя нет, Вы, Equinoxe и sup правы. Его стороны по 1 можно прибавить к двум сторонам по 10, тогда получится выпуклый четырёхугольник со сторонами $10,10,11,11$. Если так можно?

[ИСН]

Слушайте, ну ведь 10 сообщений назад sup уже доказал, что максимальный многоугольник - вписанный.