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

08/12/2018 by Руслан Масальский

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

Код

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

#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] — количество точек в многоугольнике.

Ссылки

ideone
e-olymp

Related Images:

ML 9

23/09/2015 by Антон Локтев

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

Условие:

Определить периметр правильного [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

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main(){ 
	double m,R;
	cin >> m >> R;
	cout << 2*R*sin(M_PI/m)*m;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double m,R;

cin >> m >> R;

cout << 2*R*sin(M_PI/m)*m;

return 0;

}

Код на сайте 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.

Related Images:

ML8

23/09/2015 by Настя Ивасенко

Задача. Определить периметр правильного [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].

Код

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
	int n;
	double r;
	cin >> n >> r;
	cout << (2*n*r/tan(M_PI*(n-2)/(2*n))) << endl;
	return 0;
}