Элементы вычислительной геометрии
Программирование - одна из наиболее трудных отраслей прикладной математики: слабым (poor) математикам лучше оставаться чистыми (pure) математиками. Э. Дейкстра Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольники и т.п. Результатом может быть либо ответ на какой-то вопрос, либо какой-то геометрический объект. Псевдоскалярное (косое) произведение векторов Одной из самых полезных формул при решении олимпиадных задач с элементами вычислительной геометрии является формула вычисления псевдоскалярного или косого произведения векторов. Псевдоскалярным [1] или косым произведением векторов aи b на плоскости называется число , где θ — угол вращения (против часовой стрелки) от a к b. Если хотя бы один извекторов aиbнулевой, тополагаютc=0. Геометрически псевдоскалярное произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора. С её помощью удобно работать с площадями многоугольников, выражать условия коллинеарности векторов и находить углы между ними.Псевдоскалярное произведение существует только для 2-мерных векторов Рис. 32. Псевдоскалярное (косое) произведение векторов. В большинстве случаев, когда приходится использовать формулу косого произведения, она применяется для определения площади параллелограмма (см. рис.) при заданных координатах его вершин. Рис. 33. Площадь параллелограмма по трем вершинам в координатной плоскости. Площадь произвольного многоугольника Площадь многоугольника, образованного замкнутой ломаной без самопересечений, заданной своими вершинами в порядке обхода, вычисляется по формуле [4]:
Задача №194. Площадьмногоугольника Заданы координаты n последовательных вершин многоугольника. Определить его площадь. Входные данные Первая строка содержит количество вершин многоугольника N. В следующих n строках через пробел заданы целочисленные координаты его последовательных вершин xi, yi. Известно, что 3 ≤ N ≤ 1000, -1000 ≤ xi, yi ≤ 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; }
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (480)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |