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

ML 9

Данная задача находится здесь.

Условие:

Определить периметр правильного [latex] m [/latex]-угольника, вписанного в окружность радиуса [latex] R [/latex].

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

Количество сторон правильного многоугольника [latex] m [/latex] и радиус [latex] R [/latex] описанной около него окружности.

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

Единственное число — периметр заданного многоугольника.

Тесты:

m R P
1 3 4 20.7846
2 6 5 30
3  8 13  79.5982
4 27 20 125.38

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

Код на сайте ideone.com можно получить здесь.

Убедиться в корректности формулы с помощью онлайн-калькулятора можно на этом сайте.

Решение:

Для решения данной задачи воспользуемся формулой для нахождения длины стороны правильного многоугольника с помощью радиуса описанной окружности: [latex]a=2\cdot R\cdot\sin{\frac{\pi}{m}}[/latex] , где [latex]R[/latex] — радиус описанной окружности, а [latex]m[/latex] — количество сторон правильного многоугольника. В задаче необходимо найти периметр, т.е. общую длину всех сторон: [latex]P=a\cdot m[/latex] . Таким образом, объединив формулы, получаем конечную формулу для нахождения периметра правильного многоугольника: [latex]P=\left(2\cdot R\cdot\sin{\frac{\pi}{m}}\right)\cdot m[/latex] , значение которой и необходимо вывести.

Источник формул : wikipedia.

 

 

ML8

Задача. Определить периметр правильного [latex]n[/latex]-угольника, описанного около окружности радиуса [latex]r[/latex].

Тесты

[latex]n[/latex] [latex]r[/latex] [latex]P[/latex]
4 2 16
3 5 51.9615
7 3 20.2261
5 5 36.3271
6 6 41.5692

Решение

Величину угла можно найти если задано только количество вершин — [latex]\frac{\pi\cdot(n-2))}{n}[/latex].

Для примера можно рассмотреть квадрат.
Без імені
Так как квадрат — правильный четырёхугольник, то центр вписанной окружности совпадает с центром описанной окружности.  [latex]R[/latex]  делит угол напополам — [latex]\frac{\alpha }{2}[/latex].  Отсюда получаем треугольник:

Без імені

[latex]\frac{\alpha }{2}[/latex] — половина угла квадрата, [latex]\frac{a}{2}[/latex] — половина стороны. Так как [latex]r[/latex] проходит перпендикулярно к стороне [latex]a[/latex], то мы можем воспользоваться формулой тангенса — [latex]tg\frac{\alpha }{2}=\frac{r}{0.5a}=\frac{2r}{a}[/latex] .

[latex]a=\frac{2r}{tg\frac{\alpha }{2}}[/latex].

Выводим формулу только с  [latex]n[/latex] и [latex]r[/latex].

[latex]P=\frac{2nr}{tg(\frac{\pi(n-2)}{2n})}[/latex].

Код

Код можно увидеть здесь