EduBrick

E. Обстрел флагмана

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

Корабль — выпуклый многоугольник из nn вершин, перечисленных против часовой стрелки. По нему выпустили mm ракет; известны точки взрывов. Посчитайте, сколько взрывов пришлось в корабль — то есть сколько точек лежит внутри многоугольника или на его границе.

Формат ввода

В первой строке — числа nn и mm (3≤n≤1053 \le n \le 10^5, 0≤m≤1050 \le m \le 10^5). В следующих nn строках — вершины против часовой стрелки. В следующих mm строках — точки взрывов. Координаты целые, по модулю не больше 10910^9.

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

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

Примеры

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