Элементы вычислительной геометрии

Программирование - одна из наиболее трудных отраслей прикладной математики: слабым (poor) математикам лучше оставаться чистыми (pure) математиками.

Э. Дейкстра

Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольники и т.п. Результатом может быть либо ответ на какой-то вопрос, либо какой-то геометрический объект.

Псевдоскалярное (косое) произведение векторов

Одной из самых полезных формул при решении олимпиадных задач с элементами вычислительной геометрии является формула вычисления псевдоскалярного или косого произведения векторов.

Псевдоскалярным [1] или косым произведением векторов aи b на плоскости называется число       ,

где θ — угол вращения (против часовой стрелки) от a к b. Если хотя бы один извекторов aиbнулевой, тополагаютc=0. Геометрически псевдоскалярное произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора. С её помощью удобно работать с площадями многоугольников, выражать условия коллинеарности векторов и находить углы между ними.Псевдоскалярное произведение существует только для 2-мерных векторов

Рис. 32. Псевдоскалярное (косое) произведение векторов.

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

Рис. 33. Площадь параллелограмма по трем вершинам в координатной плоскости.

Площадь произвольного многоугольника

Площадь многоугольника, образованного замкнутой ломаной без самопересечений, заданной своими вершинами в порядке обхода, вычисляется по формуле [4]:

Задача №194.  Площадьмногоугольника

Заданы координаты n последовательных вершин многоугольника. Определить его площадь.

Входные данные

Первая строка содержит количество вершин многоугольника N. В следующих n строках через пробел заданы целочисленные координаты его последовательных вершин x_i, y_i.

Известно, что 3 ≤ N ≤ 1000, -1000 ≤ x_i, y_i ≤ 1000`.

Выходные данные

Площадь многоугольника S, вычисленная с точностью до трех десятичных знаков.

Пример

Решение

Воспользуемся формулой площади многоугольника

#include<iostream>

#include<iomanip>

#include<cmath>

usingnamespace std;

int main(){

int n, x1, x2, y1, y2, x, y;

double s=0;

cin >> n >> x >> y;

x1=x;

y1=y;

for (int i=0; i<n-1; i++) {

   cin >> x2 >> y2;

   s+=(x1+x2)*(y2-y1);

   x1=x2;

   y1=y2;

}

s+=(x+x2)*(y-y2);

cout << fixed << setprecision(3) << abs(s)/2;

}