Республиканская олимпиада по информатике 2009 года за 10 класс | Казахстанские олимпиады

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

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

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

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

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

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

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

Примеры

Вход

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

Выход

8.00
8.00