e-olymp 8357. Точка в многоугольнике

Задача

Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

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

В первой строке заданы три числа: [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

Код программы

#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;
}

#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;

}

Решение

Задача сводится к поиску площадей. Считаю площадь треугольника, образующегося тремя последовательными точками многоугольника. Далее считаю площади треугольников которые заданная точка образует с каждой парой точек из этой пары. Если площадь первого треугольника равна сумме площадей этих, то точка находится в треугольнике, а следовательно и в многоугольнике. Если нет перехожу к следующей тройке точек. Если точка не принадлежит ни одному треугольнику, то точка находится вне многоугольника.