D. Точка в многоугольнике

1000 мс · 256 МБ · всё или ничего

Дан простой многоугольник — не обязательно выпуклый — и точка. Определите, лежит ли точка внутри многоугольника или на его границе.

Формат ввода

В первой строке — число $N$ ( $3 \le N \le 10^5$ ) и координаты точки. В следующих $N$ строках — координаты вершин многоугольника в порядке обхода. Все координаты целые, по модулю не больше $10^6$ .

Формат вывода

Выведите YES, если точка лежит внутри многоугольника или на его границе, и NO иначе.

Примеры

ввод

вывод

YES

ввод

4 1000000 500000
0 0
1000000 0
1000000 1000000
0 1000000

вывод

YES

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.