Глубина вложенности
3000 мс · 256 МБ · всё или ничего
Даны вложенных друг в друга выпуклых заборов: они не пересекаются и не касаются, и точка лежит внутри каждого. Для каждой из точек скажите, внутри скольких заборов она находится (граница считается «внутри»).
Формат ввода
В первой строке — число (). Дальше описаний: число и пар координат вершин против часовой стрелки. Суммарное число вершин не больше . Затем число () и пар координат. Координаты целые, по модулю не больше .
Формат вывода
Для каждой точки выведите количество заборов, внутри которых она лежит.
Примеры
ввод
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
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.