Здравствуйте, Sinclair, Вы писали:

S>Ты намекаешь, что у многоугольника максимальной площади все вершины лежат на одной окружности? Интуитивно похоже, но вот доказать что-то не могу .

Это, оказывается, теорема Крамера
площадь многоугольника с данными длинами сторон максимальна, когда многоугольник — вписанный.

я вроде уже дал ссылку где обсуждалась эта задача?

там же есть доказательство того, что площадь не зависит от перестановки сторон.

Здравствуйте, Sinclair, Вы писали:

S>Здравствуйте, McSeem2, Вы писали:
MS>>Значит надо вычислить координаты вершин сначала. Это делается элементарно. Располагаем все отрезки вдоль оси 0X, начиная с нуля. Получается такая "колбаса". А затем предполагаем, что эта колбаса существует у нас в полярных координатах, где конец колбасы соответствует 2*pi. И преобразуем из полярных координат в декартовы.
S>Ты намекаешь, что у многоугольника максимальной площади все вершины лежат на одной окружности? Интуитивно похоже, но вот доказать что-то не могу .

Сначала можно разобраться с четырёхугольником (т.е. доказать, что площадь максимальна, когда сумма противоположных углов равна "пи"; здесь все методы одинаково хороши, вплоть до прямого решения задачи на условный экстремум: максимизируем площадь как функцию двух противоположных углов, условие — два применения теоремы косинусов).

Теперь разберёмся со случаем произвольного выпуклого многоугольника. произвольные четыре его вершины, идущие подряд. Они отсекают от всего многоугольника четырёхугольник. В случае, если весь многоугольник имеет наибольшую возможную площадь, этот четырёхугольник среди всех четырёхугольников с такими же длинами сторон (!) также имеет наибольшую площадь и — по уже доказанному — может быть вписан в окружность.

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

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

Здравствуйте, Witeboragon, Вы писали:

W>Здравствуйте, Sinclair, Вы писали:

S>>Ты намекаешь, что у многоугольника максимальной площади все вершины лежат на одной окружности? Интуитивно похоже, но вот доказать что-то не могу .

W>Это, оказывается, теорема Крамера
W>площадь многоугольника с данными длинами сторон максимальна, когда многоугольник — вписанный.

W>я вроде уже дал ссылку где обсуждалась эта задача?

W>там же есть доказательство того, что площадь не зависит от перестановки сторон.

Пока писал своё доказательство, выяснилось, что это здесь уже обсуждалось...

В начале одного из предложений.

Здравствуйте, Witeboragon, Вы писали:

W>Это олимпиадная задача!
W>...
W>надеюсь не испортил пиршество мысли

Мда... автору ветки — дружная презрительная ухмылка %)))

Здравствуйте, Аноним, Вы писали:

А>При таком способе у вас вместо длин в заданной пропорции оказываются углы. Это совсем не одно и то же.

Ты прав. Длины отрезков при расположении их вдоль 0X надо корректировать. Чувствую, что это просто, типа акрсинуса. Вопрос — как конкретно?

Здравствуйте, Witeboragon, Вы писали:

W>я вроде уже дал ссылку где обсуждалась эта задача?

W>там же есть доказательство того, что площадь не зависит от перестановки сторон.

Это значит, что все, что требуется вычислить — это радиус описывающей окружности для нашего "надутого" многоугольника (прошу прощения за идиотскую терминологию). Берем площадь круга и вычитаем из нее площади "ломтиков", образованных хордами.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Witeboragon, Вы писали:

MS>Это значит, что все, что требуется вычислить — это радиус описывающей окружности для нашего "надутого" многоугольника (прошу прощения за идиотскую терминологию). Берем площадь круга и вычитаем из нее площади "ломтиков", образованных хордами.

да, именно так. основное тут понять что все вершины многоугольника
максимальной площади лежат на одной окружности, дальше дело техники

W>да, именно так. основное тут понять что все вершины многоугольника
W>максимальной площади лежат на одной окружности, дальше дело техники

Да, но как вычислить радиус этой окружности? Чувствую, что элементарно. Что-то такое вертится на уме, но сообразить не могу. Помогите люди-добры, а то ведь кошмары приснятся.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, Alglib, Вы писали:

MS>>>Значит надо вычислить координаты вершин сначала. Это делается элементарно. Располагаем все отрезки вдоль оси 0X, начиная с нуля. Получается такая "колбаса". А затем предполагаем, что эта колбаса существует у нас в полярных координатах, где конец колбасы соответствует 2*pi. И преобразуем из полярных координат в декартовы.

A>>Т.е. порядок следования отрезков не важен, для максимальной площади?

MS>Не знаю. Вообще-то, о порядке отрезков в моем сообщении речи не было вообще. Можно, например отсортировать их как-то.

Просто, максимальная площадь не будет инвариантна относительно перестановки отрезков.

Если взять, например, четыре отрезка длин а,а,в,в. То при расстановке авав максимальная площадь будет у прямоугольника = ав, а если авав то площадь будет ав sin(u) и если а<b, то u не будет равен 90 градусов, т.е. sin(u)<1.

Здравствуйте, McSeem2, Вы писали:

W>>да, именно так. основное тут понять что все вершины многоугольника
W>>максимальной площади лежат на одной окружности, дальше дело техники

MS>Да, но как вычислить радиус этой окружности? Чувствую, что элементарно. Что-то такое вертится на уме, но сообразить не могу. Помогите люди-добры, а то ведь кошмары приснятся.

блин, действительно.. похоже тут все не так просто.

для треугольника можно найти площадь по формуле Герона (p-полупериметр)
S*S = (p-a)*(p-b)*(p-c)

для (вписанного) четырехугольника (тоже именная вроде)
S*S = (p-a)*(p-b)*(p-c)*(p-d)

может для произвольного вписанного находится как
S*S = (p-a1)*(p-a2)*(p-a3)*...*(p-aN)

вроде красиво.. а? доказать не могу

W>Это олимпиадная задача!

И что из того? Не боги горшки обжигают.
Я чувствовал, что задачка с подвохом, когда мне ее предложили

Здравствуйте, Alglib, Вы писали:

A>Если взять, например, четыре отрезка длин а,а,в,в. То при расстановке авав максимальная площадь будет у прямоугольника = ав, а если авав

Наверное, имелось в виду аавв. В общем, смысл понятен.

A>то площадь будет ав sin(u) и если а<b, то u не будет равен 90 градусов, т.е. sin(u)<1.

Как так?!


Все треугольники здесь конгруэнтны, если еще кто-то помнит это слово — можете проверить.
Следовательно, площади четырехугольников на верхнем и нижнем рисунках одинаковы. Далее. Площадь верхнего четырехугольника максимальна? Да, поскольку это прямоугольник! Следовательно и площадь нижнего тоже максимальна, поскольку площади равны. Радиусы окружностей тоже одинаковы. Все вписано и все точки лежат на окружности.

Здравствуйте, Ranger_XL, Вы писали:

W>>Это олимпиадная задача!

R_X>И что из того? Не боги горшки обжигают.
R_X>Я чувствовал, что задачка с подвохом, когда мне ее предложили

Да ничего, задача-то действительно интересная.
Это я к тому что должно быть красивое решение

W>для треугольника можно найти площадь по формуле Герона (p-полупериметр)
W>S*S = (p-a)*(p-b)*(p-c)

Тут ошибочка:
S*S = p(p-a)(p-b)(p-c)

W>может для произвольного вписанного находится как
W>S*S = (p-a1)*(p-a2)*(p-a3)*...*(p-aN)

Если формула правильная, то решение тривиально
Для четырехугольника формула правильная!

Здравствуйте, Witeboragon, Вы писали:

W>для треугольника можно найти площадь по формуле Герона (p-полупериметр)
W>S*S = (p-a)*(p-b)*(p-c)

Всё-таки S*S=p*(p-a)*(p-b)*(p-c).

W>может для произвольного вписанного находится как
W>S*S = (p-a1)*(p-a2)*(p-a3)*...*(p-aN)

А это, вообще говоря, неверно. Хотя бы из соображений размерности бред получается...

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Witeboragon, Вы писали:

W>>для треугольника можно найти площадь по формуле Герона (p-полупериметр)
W>>S*S = (p-a)*(p-b)*(p-c)

А>Всё-таки S*S=p*(p-a)*(p-b)*(p-c).

W>>может для произвольного вписанного находится как
W>>S*S = (p-a1)*(p-a2)*(p-a3)*...*(p-aN)

А>А это, вообще говоря, неверно. Хотя бы из соображений размерности бред получается...

нда. но должно же быть красивое решение? может S в куб возвести

Здравствуйте, Аноним, Вы писали:

А>нда. но должно же быть красивое решение? может S в куб возвести

Кубический корень в планиметрии... Это было бы мощно
А что касается нужной задачи — ещё подумаю...

Да я тут затупил похоже

Здравствуйте, Alglib, Вы писали:

A>Да я тут затупил похоже

Ничего страшного, случается. Со мной такое происходит регулярно.