EduBrick

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

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

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

Формат ввода

В первой строке - число вершин nn (3≤n≤20003 \le n \le 2000).

В следующих nn строках - координаты вершин по контуру; многоугольник простой.

Далее число запросов qq (1≤q≤20001 \le q \le 2000) и qq строк с координатами точек. Все координаты целые, по модулю не превосходят 10410^4.

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

Для каждой точки выведите INSIDE, BORDER или OUTSIDE.

Примеры

ввод
4
0 0
4 0
4 4
0 4
3
2 2
0 0
5 5
вывод
INSIDE
BORDER
OUTSIDE
ввод
3
0 0
4 0
0 4
4
1 1
2 2
3 3
0 2
вывод
INSIDE
BORDER
OUTSIDE
BORDER
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.