凸包2

A 和 B 进行一个游戏。A 给出一个凸多边形，B 使用一条直线将其分成两部分。若两部分的面积差不超过 $\delta$，则 B 保留整个凸多边形；否则，B 去除面积较小的部分，仅保留面积较大的部分。若直线与当前凸多边形不相交，B 也会保留整个凸多边形。

每次游戏开始前，B 会给出 $n$ 条直线。A 需要决定使用这 $n$ 条直线切割凸多边形的顺序，使最终剩余图形的面积最大。

输入格式

第一行输入一个正整数 $k$，表示初始凸多边形的顶点数。

接下来 $k$ 行，每行输入两个整数 $X_i,Y_i$，按逆时针顺序给出凸多边形的各个顶点坐标。

第 $k+2$ 行输入一个正整数 $n$，表示直线的数量。

接下来 $n$ 行，每行输入 $4$ 个整数 $X_{i,1},Y_{i,1},X_{i,2},Y_{i,2}$，表示第 $i$ 条直线上的两个不同点。

最后一行输入一个非负实数 $\delta$，且 $\delta<10^4$。

输出格式

输出一个实数，表示最终可能得到的最大面积，保留 $5$ 位小数。

计算精度达到 $10^{-8}$ 即可。

样例输入

4
-100 -100
100 -100
100 100
-100 100
1
-1 0 1 0
0

样例输出

40000.00000

数据范围

• 所有给定坐标均为整数，且绝对值不超过 $500$；
• 每组输入数据中的点保证不存在任意三点共线；
• 对于 $50\%$ 的数据，$n\le 8$；
• 对于 $100\%$ 的数据，$n\le 9$，$k\le 20$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4
-100 -100
100 -100
100 100
-100 100
1
-1 0 1 0
0

输出

40000.00000