Задача
Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.
Входные данные
В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Выходные данные
Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.
Тесты
Входные данные | Выходные данные |
3 0 0 1 0 0 1 1 1 |
NO |
4 3 2 0 0 1 5 5 5 6 0 |
YES |
3 5 6 2 3 8 0 -1 -3 |
NO |
4 -2 3 0 0 5 0 0 6 3 3 |
NO |
5 3 1 9 2 3 0 -2 -4 -4 0 -4 5 |
YES |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std; struct point { int x; int y; }; int f (point *p, int N, int x, int y) { int i1, i2, n, S, S1, S2, S3, flag; for (n = 0; n < N; n++) { flag = 0; i1 = n < N-1 ? n + 1 : 0; while (flag == 0) { i2 = i1 + 1; if (i2 >= N) i2 = 0; if (i2 == (n < N-1 ? n + 1 : 0)) break; S = abs (p[i1].x * (p[i2].y - p[n].y) + p[i2].x * (p[n].y - p[i1].y) + p[n].x * (p[i1].y - p[i2].y)); S1 = abs (p[i1].x * (p[i2].y - y) + p[i2].x * (y - p[i1].y) + x * (p[i1].y - p[i2].y)); S2 = abs (p[n ].x * (p[i2].y - y) + p[i2].x * (y - p[n].y) + x * (p[n].y - p[i2].y)); S3 = abs (p[i1].x * (p[n].y - y) + p[n].x * (y - p[i1].y) + x * (p[i1].y - p[n].y)); if (S == S1 + S2 + S3) { flag = 1; break; } i1++; if (i1 >= N) i1 = 0; } if (flag == 0) break; } return flag; } int main() { int n, x, y; cin >> n >> x >> y; point* p = new point[n]; for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y; cout << (f(p, n, x, y) ? "YES" : "NO"); return 0; } |
Решение
Задача сводится к поиску площадей. Считаю площадь треугольника, образующегося тремя последовательными точками многоугольника. Далее считаю площади треугольников которые заданная точка образует с каждой парой точек из этой пары. Если площадь первого треугольника равна сумме площадей этих, то точка находится в треугольнике, а следовательно и в многоугольнике. Если нет перехожу к следующей тройке точек. Если точка не принадлежит ни одному треугольнику, то точка находится вне многоугольника.
Спасибо, исправил.