Основы программирования

Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границ. Определить площадь многоугольника.

Входные данные:
- Число вершин в многоугольнике
- Координаты вершин, заданные в порядке обхода его границы по часовой стрелке
Выходные данные:
- Площадь заданного многоугольника

Решение.
Пусть дан многоугольник ABCDE (рис.1).
Количество вершин n = 5.
Отпустим от каждой вершины перпендикуляр на ось ox.
Площадь нашего многоугольника можно посчитать через интегралы:
S = ∫AB - ∫CB + ∫CD - ∫ED + ∫EA
Получается, что каждый интеграл представляет собой площадь соответствующей трапеции. Таким образом:
S = S _ABJH – S _CBJF + S _CDIF – S _EDIG + S _EAHG
Иначе говоря, у нас есть две вершины: i и i+1. Если вершина i+1 расположена справа от вершины i, то эту площадь мы прибавляем, если слева – отнимаем.
----------------------------------------------------------------------------------
Sтрапеции = 1/2 *((a+b))*h, где a, b – основания трапеции, h – высота трапеции.
----------------------------------------------------------------------------------
Чтобы избавиться от 1/2 умножим все на 2.
2*S = (y₂ + y₁)*(x₂ – x₁) – (y₂ + y₃)*(x₂ – x₃) + (y₄ + y₃)*(x₄ – x₃) – (y₄ + y₅)*(x₄ – x₅) + (y₁ + y₅)*(x₁ – x₅) = y₂*x₂ – y₂*x₁ + y₁*x₂ – y₁*x₁ – y₂*x₂ + y₂*x₃ – y₃*x₂ + y₃*x₃ + y₄*x₄ – y₄*x₃ + y₃*x₄ – y₃*x₃ – y₄*x₄ + y₄*x₅ – y₅*x₄ + y₅*x₅ + y₁*x₁ – y₁*x₅ + y₅*x₁ – y₅*x₅ = x₁ *(y₅ – y₂) + x₂*(y₁ – y₃) + x₄*(y₃ – y₅) + x₅*(y₄ – y₁)
Отсюда видно, что
S = |∑(x[i] * (y[i-1] - y[i+1]))| / 2 , от i = 0 до i = n-1.
где (x₀, y₀) = (x_n, y_n)

Программа:

#include <iostream.h>
#include <conio.h>
#include <math.h>
#include <graphics.h>
int x[100];  
int y[100];   //  массив вершин многоугольника (не более 100 точек)
 
int main()
{
   clrscr();  
   int i, n;
   long s, res = 0, sq = 0;
 
   cout << "Enter the number of vertices:" << endl;
   cin >> n;
 
   cout << "Enter coordinates:" << endl;
   for (i = 0; i < n; i++) {
     cin >> x[i]; // координата x
     cin >> y[i]; // координата y
   }
 
 
   int gd, gm;
   gd = DETECT;
   initgraph (&gd, &gm, "c:\\temp");
 
   // построение на экране многоугольника
   for (i = 0; i < n; i++) {   
     circle (x[i] + 150, y[i] + 150, 2);
     if (i == n - 1) {
       i = 0;
       line (x[i] + 150, y[i] + 150, x[n-1] + 150, y[n-1] + 150);
       break;
     }
     line (x[i] + 150, y[i] + 150, x[i+1] + 150, y[i+1] + 150);
   }
 
   // Расчет площади многоугольника через сумму площадей трапеций 
   for (i = 0; i < n; i++) {
     if (i == 0) {
       s = x[i]*(y[n-1] - y[i+1]); //если i == 0, то y[i-1] заменяем на y[n-1]
       res += s;
     }
     else
       if (i == n-1) {
	 s = x[i]*(y[i-1] - y[0]); // если i == n-1, то y[i+1] заменяем на y[0]
	 res += s;
       }
     else {
       s = x[i]*(y[i-1] - y[i+1]);
       res += s;
     }
   }
   sq = abs(res/2);
   cout << "-------------" << endl;
   cout << "Square:" << endl;
   cout << sq;
   getch();
 
   return 0;
}