408743: GYM103286 G Рудольф и разрезы

G. Рудольф и разрезыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Рудольф долгое время ходил по магазину канцелярских товаров в поисках особенной ручки для его особенных заметок. Уже увидев нужную ему ручку, Рудольф обратил внимание на очень странный аппарат. Это была какая-то платформа с лезвием. Он обратился к консультантам магазина, и ему объяснили, что это просто резак для бумаг, который позволяет сделать один ровный и длинный разрез на листе бумаги.

Рудольф решил купить чудо-устройство и сразу же испытать его, но ... слегка увлекся. Очнувшись от охватившего его бумажного азарта, он задумался.

Рудольфа мучали две мысли:

1. После выполнения $$$M$$$ разрезов получилась какая-то фигура. Какой же она площади?
2. Зачем Рудольф так сильно изрезал листок?

Если второй вопрос скорее риторический, то первый вопрос стал для Рудольфа критически важным. Известно, что изначально у Рудольфа был лист бумаги, который помещался в резак. Лист бумаги имел форму произвольного многоугольника без самопересечений. Рудольф запомнил, какие координаты на координатной плоскости резака соответствовали вершинам многоугольника, описывающего лист бумаги, и по каким линиям он делал разрез. Стоит заметить, что после выполнения каждого разреза Рудольф убирал некоторые отрезанные части.

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

Входные данные

Первая строка содержит одно целое число $$$N$$$ $$$(4 \leq N \leq 100)$$$ — количество вершин листа Рудольфа перед первым разрезом.

Следующие $$$N$$$ строк содержат по два целых числа $$$X_i, Y_i$$$ $$$(0 \leq X_i, Y_i \leq 1000)$$$ — координаты $$$i$$$-й вершины листа. Точки перечислены в том порядке, в котором они соединяются, чтобы образовать контур листа.

Следующая строка содержит одно целое число $$$M$$$ $$$(0 \leq M \leq 100)$$$ — количество разрезов, которые сделал Рудольф.

Следующие $$$M$$$ строк содержат четыре целых числа $$$X_l, Y_l, X_r, Y_r$$$ $$$(-1000 \leq X_l, Y_l, X_r, Y_r \leq 2000)$$$ и один символ $$$H$$$ — описание координат точек, между которыми был произведен разрез, и указание, какие из частей листа были убраны.

$$$H$$$ может принимать два значения:

• «U» — Рудольф убирал части листа, которые были выше линии разреза.
• «B» — Рудольф убирал части листа, которые были ниже линии разреза.

Гарантируется, что линия разреза, если проходит через лист, то всегда пересекает лист полностью.

Выходные данные

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

Ваш ответ будет засчитан, если относительная или абсолютная погрешность не будет превышать $$$10^{-4}$$$. Формально если $$$a$$$ — ваш ответ, а $$$b$$$ — ответ жюри, то он будет засчитан если $$$\frac{|a-b|}{max(b,1)} \leq 10^{-4}$$$.

ПримерыВходные данные

4
0 0
1 0
1 3
0 3
1
-1 1 2 1 B

Выходные данные

2.000000

Входные данные

4
1 1
7 1
7 9
1 9
2
-1 8 9 8 U
-1 5 5 -1 B

Выходные данные

40.000000

Входные данные

16
4 0
11 0
11 2
5 2
5 4
8 4
8 6
2 6
2 8
4 8
4 10
0 10
0 8
1 8
1 4
4 4
2
0 11 11 0 B
-5 1 12 1 U

Выходные данные

0.500000

Входные данные

4
0 0
1 0
1 1
0 1
1
-1 2 3 2 B

Выходные данные

0.000000

Примечание

Изображение ниже описывает второй тест. Серые области обозначают части листа, которые были убраны после разрезов.