Задача. Площадь многоугольника
Условие задачи
Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.
Входные данные
Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].
Выходные данные
Площадь многоугольника [latex]S[/latex], вычисленная с точностью до трех десятичных знаков.
Также условие задачи можно посмотреть здесь.
Тестирование
| № | Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex]) | Выходные данные |
| 1. | 3, (0, 0), (0, 2), (2, 0) | 2.000 |
| 2. | 4, (-1000, 500), (-500, 1000), (2, 10), (35, 60) | 339865.000 |
| 3. | 10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6) | 124562.500 |
| 4. | 5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2) | 1446.000 |
Реализация
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> #include <iomanip> #include <cmath> using namespace std; int main() { int n, x1, x2, y1, y2, x, y; double sum=0; cin >> n >> x >> y; x1=x; y1=y; for (int i=0; i<(n-1); i++) { cin >> x2 >> y2; sum=sum+(x1+x2)*(y2-y1); x1=x2; y1=y2; } sum=sum+(x+x2)*(y-y2); cout << fixed << setprecision(3) << abs(sum) / 2 << endl; return 0; } |
Алгоритм решения
Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].
Подробнее о вычислении площади произвольного многоугольника можно прочесть здесь.
Для запроса на выполнение перейдите по ссылке.
Ссылка на засчитанное решение на e-olymp.com.