Матч
166, Выпуклый многоугольник (ConvexPolygon)
Дивизион 2, Уровень
3
Координаты вершин выпуклого
многоугольника заданы в массивах x и y в порядке их последовательного
обхода. Вычислить площадь многоугольника.
Класс: ConvexPolygon
Метод: double
findArea(vector<int> x, vector<int> y)
Ограничения:
x и y содержат от 3 до 50 элемнтов, -10000 £ x[i], y[i] £ 10000, многоугольник выпуклый и без
самопересечений.
Вход. Абсциссы вершин многоугольника заданы в массиве x, а соответствующие им
ординаты в массиве y.
Выход. Площадь выпуклого многоугольника.
Пример входа
|
x |
y |
|
{0,0,1} |
{0,1,0} |
|
{-10000,-10000,10000,10000} |
{10000,-10000,-10000,10000} |
|
{100,80,30,-30,-80,-100,-80,-30,30,80} |
{0,58,95,95,58,0,-58,-95,-95,-58} |
Пример выхода
0.5
4.0E8
29020.0
РЕШЕНИЕ
геометрия
Пусть (x1, y1),
(x2, y2), …, (xn,
yn) – координаты вершин
выпуклого многоугольника, заданные в порядке его обхода по или против часовой
стрелки. Тогда площадь многоугольника вычисляется по формуле трапеций:
S = abs(
)
где (xn+1, yn+1)
= (x1, y1).
ПРОГРАММА
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
class ConvexPolygon
{
public:
double findArea(vector<int>
x, vector<int> y)
{
double s;
int i;
x.push_back(x[0]); y.push_back(y[0]);
for(s = i = 0; i < x.size() - 1; i++)
s += (y[i+1] + y[i]) * (x[i+1] - x[i]) / 2.0;
return fabs(s);
}
};