EduBrick

H. Замок

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

Вокруг замка стоят nn заборов; каждый — выпуклый многоугольник, вершины перечислены против часовой стрелки. Заборы не пересекаются и не касаются друг друга, и точка (0,0)(0,0) лежит внутри каждого из них.

По двору ходят mm захватчиков. Захватчик считается опасным, если он находится внутри самого внешнего забора; перелезать через заборы никто не умеет. Посчитайте суммарную площадь области, до которой могут добраться опасные захватчики.

Формат ввода

В первой строке — число nn (1≤n≤1051 \le n \le 10^5). Дальше nn описаний заборов: число kk и kk пар координат (∣x∣,∣y∣≤2⋅106|x|, |y| \le 2 \cdot 10^6). Суммарное число вершин не превосходит 10510^5. Затем число mm (0≤m≤1050 \le m \le 10^5) и mm пар координат захватчиков.

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

Выведите суммарную захваченную площадь с шестью знаками после десятичной точки.

Примеры

ввод
3
4
-10 -10
10 -10
10 10
-10 10
4
-20 -20
20 -20
20 20
-20 20
4
-30 -30
30 -30
30 30
-30 30
3
1 1
22 23
111 123
вывод
2400.000000
ввод
1
3
-5 -5
5 -5
0 5
1
0 0
вывод
50.000000
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.