EduBrick

Глубина вложенности

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

Даны nn вложенных друг в друга выпуклых заборов: они не пересекаются и не касаются, и точка (0,0)(0,0) лежит внутри каждого. Для каждой из mm точек скажите, внутри скольких заборов она находится (граница считается «внутри»).

Формат ввода

В первой строке — число nn (1≤n≤1051 \le n \le 10^5). Дальше nn описаний: число kk и kk пар координат вершин против часовой стрелки. Суммарное число вершин не больше 10510^5. Затем число mm (1≤m≤1051 \le m \le 10^5) и mm пар координат. Координаты целые, по модулю не больше 2⋅1062 \cdot 10^6.

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

Для каждой точки выведите количество заборов, внутри которых она лежит.

Примеры

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