Народ, нашел в справочнике формулу для площади многоугольника:
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 — искомый радиус.

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

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

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

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

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