题目描述

A 和 B 玩一个游戏：

A 给出一个凸多边形，B 会用一条直线将其分成两部分。如果它们的面积差不超过一个数 $d$，B 会保留这个凸多边形，否则 B 会去除面积较小的一部分。

现在给出 $n$ 条直线，问应该用怎么样顺序用这 $n$ 条直线割凸多边形，使得剩下的图形面积最大。

注意：如果直线和凸多边形不相交，则 B 会保留这个凸多边形。

输入格式

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

接下来 $k$ 行按逆时针顺序给出多边形的顶点坐标 $X_i,Y_i$。

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

接下来 $n$ 行，每行 $4$ 个整数 $X_{i,1},Y_{i,1},X_{i,2},Y_{i,2}$，表示直线上的不重合两点的坐标。

最后一行输入一个非负实数 $D$。

输出格式

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

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

40000.00000 

数据规模与约定

对于 $50\%$ 的数据 $n\le 8$。

对于 $100\%$ 的数据 $n\le 9$，$k\le 20$。

输入数据保证所有给出的坐标值都是绝对值不超过 $500$ 的整数，$0\le d \le 1000$。

保证输入数据中的点无三点共线。

精度取 $10^{-8}$ 足够。