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

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

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

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

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

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

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

Как так?!


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

Ranger_XL wrote:
>
> Даны N отрезков разной длины, вместе составляющих выпуклый
> многоугольник. Как посчитать площадь этого многоугольника?
> Если бы были координаты точек, сделал бы триангуляцию. А так не понимаю,
> как от отрезков перейти к координатам. Может есть другие способы?
если даны только длины — то это невозможно, ромб со стороной 1 имеет
площадь от 1 до 0. Если координаты векторов — то надо их складывать, а
вершины — промежуточные результаты. Если длины и углы — тогда надо
получать сначала углы поворота относительно первого отрезка, потом
координаты сторон как векторов, а потом — координаты вершин.
А что в Вашем случае?

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

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

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

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

W>Ну, во всяком случае, не вокруг любого многоугольника можно описать окружность. Следовательно, если пытаться располагать вершины на окружности, то можно и обломаться.

А можно пример?
Или имеется в виду, что-то типа набора длин 10,2,3. Но из них вообще нельзя составить многоугольник. Я предполагаю, что набор длин таков, что из них можно составить многоугольник ненулевой площади.

Здравствуйте, 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)

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

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

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

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

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

T>В большинстве случаев многоугольник можно разбить на кучу триугольников без напряжения.Потом посчитать площадь триугольника.

Глубокая мысль Ты бы хоть исходный пост прочитал, для начала, что-ли...

Даны N отрезков разной длины, вместе составляющих выпуклый многоугольник. Как посчитать площадь этого многоугольника?
Если бы были координаты точек, сделал бы триангуляцию. А так не понимаю, как от отрезков перейти к координатам. Может есть другие способы?

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

R_X>Даны N отрезков разной длины, вместе составляющих выпуклый многоугольник. Как посчитать площадь этого многоугольника?
R_X>Если бы были координаты точек, сделал бы триангуляцию. А так не понимаю, как от отрезков перейти к координатам. Может есть другие способы?

Ну раз есть N отрезков, значит можно так или иначе получить координаты. А иначе какие же эти отрезки? Таким образом, главный вопрос звучит так: "что такое отрезок?"
А площадь считается элементарно, причем не только для выпуклых:
http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/
Мы кроме площади узнаем еше и направление обхода:
http://astronomy.swin.edu.au/~pbourke/geometry/clockwise/index.html

R>если даны только длины — то это невозможно, ромб со стороной 1 имеет
R>площадь от 1 до 0... А что в Вашем случае?

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

R_X>Как расположить отрезки, я сообразил (отрезки, исходящие из одной вершины, должны минимально отличаться по длине?), а вот как найди площадь?

http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/source1.c

MS>http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/source1.c

Нет, я не тормоз В представленном алгоритме даны координаты вершин, а у меня только длины отрезков.

Пример: (4 отрезка) 10 4 5 5
Ответ: 28 (трапеция)

PS. Число отрезков N <= 100

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

MS>>http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/source1.c

R_X>Нет, я не тормоз В представленном алгоритме даны координаты вершин, а у меня только длины отрезков.

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

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

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

Не понимаю, можешь более подробно объяснить, как найти полярные координаты?
Кстати, а теорема sin-усов для многоугольника не справедлива?

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

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

MS>>>http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/source1.c

R_X>>Нет, я не тормоз В представленном алгоритме даны координаты вершин, а у меня только длины отрезков.

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

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

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

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

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

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

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

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

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

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

W>К тому же, звенья этой "цепи" (она же "колбаса"=) придется попереставлять между собой. Т.к. во-первых, не при всех расположениях из нее таким способом сложится многоугольник,

Как так? Может я тормоз, но что-то не вижу таких случаев, если многоугольник выпуклый.

W>а во-вторых, площади похоже будут разные, а нужно найти максимальную.

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

Если оба ответа — "да", то максимальная площадь не будет зависеть от расположения отрезков. Доказательство последнего тривиально.

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

R_X>Не понимаю, можешь более подробно объяснить, как найти полярные координаты?

У нас есть цепь ("колбаса"), расположенная вдоль 0X. Мы масштабируем все точки так, чтобы координата конца цепи была 2*pi. Запоминаем коэффициент масштабирования. После чего:
Poly[i].x = cos(x[i]);
Poly[i].y = sin(x[i]);
Получаем многоугольник, вписанный в окружность единичного радиуса. Далее масштабируем обратно. Все эти действия, включая вычисление площади можно проделать без использования дополнительной памяти, то есть массив Poly нам в общем-то не нужен. Он чисто так, для иллюстрации.

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

R_X>Даны N отрезков разной длины, вместе составляющих выпуклый многоугольник. Как посчитать площадь этого многоугольника?
R_X>Если бы были координаты точек, сделал бы триангуляцию. А так не понимаю, как от отрезков перейти к координатам. Может есть другие способы?

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

Вуаля:
http://groups.google.com/groups?q=%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D0%B0+%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F+%D0%BF%D0%BB%D0%BE%D1%89%D0%B0%D0%B4%D1%8C&amp;hl=ru&amp;lr=&amp;selm=6b5t2s%24rv%241%40mx.nsu.ru&amp;rnum=1

надеюсь не испортил пиршество мысли

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

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

W>>К тому же, звенья этой "цепи" (она же "колбаса"=) придется попереставлять между собой. Т.к. во-первых, не при всех расположениях из нее таким способом сложится многоугольник,

MS>Как так? Может я тормоз, но что-то не вижу таких случаев, если многоугольник выпуклый.

Ну, во всяком случае, не вокруг любого многоугольника можно описать окружность. Следовательно, если пытаться располагать вершины на окружности, то можно и обломаться.


W>>а во-вторых, площади похоже будут разные, а нужно найти максимальную.

MS>Здесь надо выяснить 2 вещи.
MS>1. Будет ли радиус описанной окружности одинаковым при любых расположениях отрезков в нашем "надутом" многоугольнике.
Окружности такой может и не быть вовсе (см. выше).

MS>2. Будет ли площадь максимальной, если мы расположим все точки на одной окружности.

MS>Если оба ответа — "да", то максимальная площадь не будет зависеть от расположения отрезков. Доказательство последнего тривиально.

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

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

R_X>>Не понимаю, можешь более подробно объяснить, как найти полярные координаты?

MS>У нас есть цепь ("колбаса"), расположенная вдоль 0X. Мы масштабируем все точки так, чтобы координата конца цепи была 2*pi. Запоминаем коэффициент масштабирования. После чего:
MS>Poly[i].x = cos(x[i]);
MS>Poly[i].y = sin(x[i]);
MS>Получаем многоугольник, вписанный в окружность единичного радиуса. Далее масштабируем обратно. Все эти действия, включая вычисление площади можно проделать без использования дополнительной памяти, то есть массив Poly нам в общем-то не нужен. Он чисто так, для иллюстрации.

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

Здравствуйте, 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>Это олимпиадная задача!

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

Здравствуйте, 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)

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

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

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

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

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

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

Народ, нашел в справочнике формулу для площади многоугольника:
S = r * p,
где r — радиус описанной окружности, а p — полупериметр

Осталось найти этот радиус

Ranger_XL wrote:
> Народ, нашел в справочнике формулу для площади многоугольника:
> S = r * p,
> где r — радиус описанной окружности, а p — полупериметр
Не бывает. Это радиус вписанной, что доказывается триангуляцией.

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

R>Ranger_XL wrote:
>> Народ, нашел в справочнике формулу для площади многоугольника:
>> S = r * p,
>> где r — радиус описанной окружности, а p — полупериметр
R>Не бывает. Это радиус вписанной, что доказывается триангуляцией.

неправда ваша, описанной.
Доказывается действительно триангуляцией (надо разбить на треугольники с вершиной в центре описанной окружности).

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

sin(alpha[i]) = (a[i]/2) / R => alpha(i) = arcsin(a[i]/2R)

(получается так же легго, надо разбить на треугольники с вершиной в центре)
потом можно их все сложить, получим 2*PI.

Итого: для нахождения радиуса получаем уравнение (ха-ха, все так красиво начиналось)

arcsin(a[1]/2R) + arcsin(a[2]/2R) + ... arcsin(a[N]/2R) = 2 PI.

решаем , получаем радиус, дальше умножаем на полупериметр => получаем площадь
такие дела...

Добавка:

W>arcsin(a[1]/2R) + arcsin(a[2]/2R) + ... arcsin(a[N]/2R) = 2 PI.

может от обих частей взять синус, дальше раскрыть по формуле суммы синусов, чтожет что путевое получится?

Witeboragon wrote:
> Здравствуйте, raskin, Вы писали:
>
> R>Ranger_XL wrote:
>> > Народ, нашел в справочнике формулу для площади многоугольника:
>> > S = r * p,
>> > где r — радиус описанной окружности, а p — полупериметр
> R>Не бывает. Это радиус вписанной, что доказывается триангуляцией.
>
> неправда ваша, описанной.
> Доказывается действительно триангуляцией (надо разбить на треугольники с
> вершиной в центре описанной окружности).

Может, в милой книге опечатка? Для квадрата: сторона — 1. Радиус
вписанной — 1/2. Радиус описанной — 1/sqrt(2). Площадь — 1. Полупериметр
— 2.

Это верно?
Но если да, то в формуле радиус вписанной окружности. Если нет, то у
меня совсем уже глюки.

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

R>Может, в милой книге опечатка? Для квадрата: сторона — 1. Радиус
R>вписанной — 1/2. Радиус описанной — 1/sqrt(2). Площадь — 1. Полупериметр
R>- 2.

R>Это верно?
R>Но если да, то в формуле радиус вписанной окружности. Если нет, то у
R>меня совсем уже глюки.

это у меня глюки
но все равно, полщадь можно вычислить зная радиус:
здесь h[i] — высота соотв. хорде треугольника, alpha[i] — половина угол у центра.

h[i] = R * cos(alpha[i])

sin(alpha[i]) = a[i] / R

S[i] = 2 * (h * a[i]/2) = R * a[i] * sqrt[1 — (a[i]/R)^2]

S = Summ(S[i])

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

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

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

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

R_X>Народ, нашел в справочнике формулу для площади многоугольника:
R_X> S = r * p,
R_X>где r — радиус описанной окружности, а p — полупериметр

Сорри за невнимательность, r — радиус вписанной окружности

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

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

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

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

Боюсь, всё не очень-то и просто. Кроме банального определения радиуса описанной окружности,
типа, из уравнения arcsin(a[1]/2r)+arcsin(a[2]/2r)+...+arcsin(a[n]/2r)=ПИ, где a[1..n]
суть массив заданных длин сторон, а r — искомый радиус.

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

В большинстве случаев многоугольник можно разбить на кучу триугольников без напряжения.Потом посчитать площадь триугольника.