Республиканская олимпиада по информатике 2009 год

Задача F. Магазины

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Город представляет собой выпуклый многоугольник. В городе имеется несколько магазинов. Каждый житель города ходит только в ближайший к нему магазин. Если ближайших магазинов несколько, то житель никуда не ходит. Для каждого магазина посчитайте, площадь территории, жители которой ходят в этот магазин.

Формат входного файла

Первая строка содержит целое число $N$ — количество вершин многоугольника, представляющего город ($3 \le N \le 50$). Каждая из следующих $N$ строк содержит по $2$ целых числа — координаты вершин в порядке обхода против часовой стрелки. Следующая строка содержит целое число $M$ — количество магазинов в городе ($1 \le M \le 50$). Каждая из следующих $M$ строк содержит по $2$ целых числа — координаты магазинов ($i$-я строка - координаты $i$-го магазина). Все точки различны. Координаты точек не превышают по абсолютному значению $10000$. Числа в строках разделены пробелами.

Формат выходного файла

Выведите $M$ вещественных чисел через пробел: $i$-е число — площадь, обслуживаемая $i$-м магазином округленная до двух цифр после десятичной точки.

Пример:

Вход

4
0 0
4 0
4 4
0 4
2
1 2
3 2

Ответ

8.00
8.00

Гарантируется, что в некотором подмножестве тестов, суммарно не превышающем $50$ баллов, $M \le 2$.