Re: Найти площадь многоугольника

From

Oleg Polubasoff ()

To

All

Date

2000-02-28T13:59:03Z

Area

RU.ALGORITHMS

From: "Oleg Polubasoff" <pbas@spb.cityline.ru>

    Привет, Иван!

27.02.2000  21:06, Ivan Voroshilin wrote:

IV> Решал я задачу на олимпиаде по программированию следующего содержания:
IV> Вводим кол-во вершин многоугольника и коорд-ты (x,y) каждой вершины.
IV> Необходимо вычислить площадь этого многоугольника.
IV> Для выпуклого я конечно же сделал... Но в задании было написано, чтобы
IV> высчитывало площадь также для не выпуклого многоугольника.
IV> Может кто расскажет из знатоков как посчитать для невыпуклого
IV> многоугольника площадь?

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

Пусть X(i), Y(i), i = 1..N - координаты вершин в порядке обхода по контуру.
Многоугольник может быть невыпуклым, но без самопересечений.

Тогда S = | \sum{i = 3..N} ((Y(1)-Y(i-1)) * (X(i)-X(1)) -
- (X(1)-X(i-1)) * (Y(i)-Y(1)))| / 2.

Бастрее не бывает. :)
В частности, для треугольника (тоже часто спрашивают):

S = |(Y(1)-Y(2)) * (X(3)-X(1)) - (X(1)-X(2)) * (Y(3)-Y(1))| / 2.

    Олег Полубасов.


--- ifmail v.2.15dev4
 * Origin: Demos online service (2:5020/400)