ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Ural SU contest. Petrozavodsk training camp. Summer 2010

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

H. Охота на мух

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Пахом и его друзья решили поохотиться на мух. Каждый из них взял свою любимую мухобойку, после чего они подкрались к стене, на которой сидели n ничего не подозревающих мух. По команде друзья одновременно ударили своими мухобойками по стене так сильно, что на стене остались следы от ударов. След каждой мухобойки представляет собой простой многоугольник с внутренностью. Следы никакой пары мухобоек не имеют общих точек. Муха была убита, если она находилась внутри или на границе следа. Помогите друзьям вычислить, сколько мух убил каждый из них.

Исходные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество мух. В каждой из следующих n строк через пробел записаны координаты очередной мухи. Никакие две мухи не расположены в одной точке. В следующей строке записано целое число m (1 ≤ m ≤ 30 000) — количество мухобоек. Каждая из следующих m строк описывает след очередной мухобойки. След задаётся количеством вершин в соответствующем ему многоугольнике и координатами этих вершин в порядке обхода против часовой стрелки. Суммарное количество вершин во всех многоугольниках не превосходит 105. Все координаты целые и не превосходят по модулю 107.

Результат

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

Пример

исходные данныерезультат
3
0 0
1 1
4 4
3
3 -2 -2 -3 -3 -2 -3
3 0 0 2 0 1 1
3 3 0 5 0 4 6
0
2
1
Автор задачи: Денис Дублённых
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2010
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1848. Охота на мух