Задача взята с сайта e-olymp
Условие
Как известно, простой многоугольник — это фигура, состоящая из непересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.
Входные данные
В первой строке заданы три числа: [latex]n (3 \leq n \leq 10^5)[/latex] и координаты точки. Далее в [latex]n[/latex] строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.
Выходные данные
Вывести строку «YES«, если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.
Тесты
| № | Inputs | Outputs |
| 1 | 3 0 0 1 0 0 1 1 1 |
NO |
| 2 | 4 3 2 0 0 1 5 5 5 6 0 |
YES |
| 3 | 8 2 1 0 0 0 4 4 4 4 0 3 0 3 2 1 2 1 0 |
NO |
| 4 | 8 4 3 0 0 0 4 4 4 4 0 3 0 3 2 1 2 1 0 |
YES |
| 5 | 6 1 1 0 0 0 2 1 4 2 2 2 0 1 3 |
NO |
Код
|
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 55 56 |
#include <iostream> #include <cmath> typedef double long dl; using namespace std; const double E = 1e-6; bool on_edge(dl x, dl y, dl x1, dl y1, dl x2, dl y2) { bool res = false; if (fabs(x2 - x1) < E) { if (fabs(x - x1) < E && y > min(y1, y2) - E && y - E < max(y1, y2)) res = true; } else { x -= x1; y -= y1; x2 -= x1; y2 -= y1; if (x - E < max(x1, x2) && x > min(x1, x2) - E && fabs(x2 * y - y2 * x) < E) { res = true; } } return res; } bool cross(dl x0, dl y0, dl x1, dl y1, dl x2, dl y2){ return (y1 < y0 && y2 > y0 - E || y2 < y0 && y1 > y0 - E) && (y0 * (x1 - x2) + y1 * x2 - x1 * y2) / (y1 - y2) < x0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); dl x0, y0, xs, ys, xt, yt, xi, yi; int n; cin >> n >> x0 >> y0; cin >> xs >> ys; xt = xs; yt = ys; bool par_am = false; bool on_side = false; n--; while (n-- && !on_side) { cin >> xi >> yi; if (on_edge(x0, y0, xt, yt, xi, yi)) { on_side = true; } if (cross(x0, y0, xt, yt, xi, yi)) { par_am = !par_am; } xt = xi; yt = yi; } if (on_edge(x0, y0, xt, yt, xs, ys)) { on_side = true; } if (cross(x0, y0, xt, yt, xs, ys)) { par_am = !par_am; } cout << (par_am || on_side ? "YES" : "NO"); return 0; } |
Решение
Проверять на то, находится ли точка внутри многоугольника, будем так. Берём нашу точку и от нее проводим луч влево параллельно оси абсцисс.
Считаем количество пересечений луча со сторонами многоугольника.
Если количество пересечений чётно, то точка лежит вне многоугольника, а если количество пересечений нечётно, то точка лежит внутри многоугольника.
Нужно еще учесть момент, когда точка лежит на одной из сторон.
- x0, y0 — координаты нашей точки.
- xs, ys — координаты самой первой точки, они нам нужны чтобы проверить пересечение луча со стороной, образованной первой и последней точками.
- xi, yi — координаты точки которую вводим.
- xt, yt — координаты предыдущей точки, нужны для того, чтобы образовать сторону.
- par_am — (parity of amount) хранит четность количества пересечений луча со сторонами. Если чётное количество пересечений, то par_am = false, если нечётное, то par_am = true.
- on_side — если мы узнали, что точка лежит на одной из сторон, то дальше ничего искать не нужно.
Функция on_edge() рассматривает два случая:
- Если сторона параллельна оси [latex]Oy[/latex], посчитаем условие нахождения между минимальной и максимальной [latex]y[/latex]-координатами. Если оно справедливо, проверяем на равенство [latex]x[/latex]-координат.
- Для удобства мы подвинет отрезок и точку так чтоб начало отрезка лежало в точке [latex](0,0)[/latex]. После это проверяем находится ли точка по координате [latex]x[/latex] между концов (включительно) отрезка. Остается сравнить тангенс угла между осью [latex]Ox[/latex] и вектором [latex]x_2[/latex] [latex]y_2[/latex]с тангенсом угла между осью [latex]Ox[/latex] и вектором [latex]x[/latex] [latex]y[/latex] и если они равны, то точка [latex]x[/latex] [latex]y[/latex] лежит на отрезке (стороне) [latex]x_1, y_1, x_2, y_2 [/latex].
Считываем и запоминаем первую точку. Дальше считываем по точке, которая вместе с предыдущей образует сторону. Делаем проверку:
- Лежит ли точка [latex]x_0[/latex] [latex]y_0[/latex] на этой стороне.
- Пересекает ли луч сторону.
Чтобы проверить пересекает ли луч сторону делаем:
- Проверяем лежат ли две точки по разные стороны луча
- Строим уравнение прямой вида [latex]y = kx +b[/latex], проходящее через две точки [latex]x_i, y_i, x_t, y_t [/latex]выглядит оно так:
[latex]y = \frac{y_i-y_t}{x_i-x_t} \cdot x+(y_i-\frac{y_i-y_t}{x_i-x_t} \cdot x_i )[/latex] - Подставив вместо [latex]y[/latex] [latex]y_0[/latex], получаем что [latex]x[/latex] равен
[latex]\frac{y_0 \cdot x_i-y_0 \cdot x_t+y_i \cdot x_t-x_i \cdot y_t} {y_i-y_t}[/latex] И он должен быть меньше [latex]x_0[/latex], так как луч направлен влево.
Сложность [latex]O(n)[/latex], где [latex]n[/latex] — количество точек в многоугольнике.