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

Задача взята с сайта 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

Код

Решение

Проверять на то, находится ли точка внутри многоугольника, будем так. Берём нашу точку и от нее проводим луч влево параллельно оси абсцисс.
Считаем количество пересечений луча со сторонами многоугольника.
Если количество пересечений чётно, то точка лежит вне многоугольника, а если количество пересечений нечётно, то точка лежит внутри многоугольника.
Нужно еще учесть момент, когда точка лежит на одной из сторон.

  • x0, y0 — координаты нашей точки.
  • xs, ys — координаты самой первой точки, они нам нужны чтобы проверить пересечение луча со стороной, образованной первой и последней точками.
  • xi, yi — координаты точки которую вводим.
  • xt, yt — координаты предыдущей точки, нужны для того, чтобы образовать сторону.
  • par_am — (parity of amount) хранит четность количества пересечений луча со сторонами. Если чётное количество пересечений, то par_am = false, если нечётное, то  par_am = true.
  • on_side — если мы узнали, что точка лежит на одной из сторон, то дальше ничего искать не нужно.

Функция on_edge() рассматривает два случая:

  1. Если сторона параллельна оси [latex]Oy[/latex], посчитаем условие нахождения между минимальной и максимальной [latex]y[/latex]-координатами. Если оно справедливо, проверяем на равенство [latex]x[/latex]-координат.
  2. Для удобства мы подвинет отрезок и точку так чтоб начало отрезка лежало в точке [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].

Считываем и запоминаем первую точку. Дальше считываем по точке, которая вместе с предыдущей образует сторону. Делаем проверку:

  1. Лежит ли точка [latex]x_0[/latex] [latex]y_0[/latex] на этой стороне.
  2. Пересекает ли луч сторону.

Чтобы проверить пересекает ли луч сторону делаем:

  1. Проверяем лежат ли две точки по разные стороны луча
  2. Строим уравнение прямой вида [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]
  3. Подставив вместо [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] — количество точек в многоугольнике.

Ссылки

ideone
e-olymp

Related Images: