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

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

Здравствуйте, 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>Т.е. порядок следования отрезков не важен, для максимальной площади?

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

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

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

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

Здравствуйте, 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 нам в общем-то не нужен. Он чисто так, для иллюстрации.

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

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

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

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

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

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

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