#1838. 凸包2

内存限制:64 MiB 时间限制:10 Sec

题目描述

A和B玩一个游戏:A出一个凸多边形,B会用一条直线将其分成两部分.如果它们的 面积差不超过一个数Delta,B会保留这个凸多边形,否则B会去除面积较小的一部分每次游戏前B会给出N条直线,问A应该用怎么样顺序用这N条直线割凸多边形,使得剩下的图形面积最大.注意如果直线和凸多边形不相交,则B会保留这个凸多边形.

输入格式

第一行输入一个正整数 k,表示初始时多边形的顶点数。 以下k 行按逆时针顺序给出多边形的顶点坐标Xi,Yi。 第 k+2行输入一个正整数n,表示直线的数目。 以下n 行,每行4 个整数Xi1, Yi1, Xi2, Yi2,表示直线上的不重合两点的坐标。 最后一行输入一个小于 10000 的非负实数 delta。 输入数据保证所有给出的坐标值都是绝对值不超过 500的整数

输出格式

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

样例

样例输入


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

样例输出


			
40000.00000

精度取1e-8足够
每组输入数据中的点保证无3 点共线

数据范围与提示

对于 50%的数据 n<=8
对于 100%的数据 n<=9,k<=20