#P1838. 凸包2

    ID: 860 传统题 1000ms 64MiB 尝试: 16 已通过: 5 难度: 7 上传者: 标签>CF2200提高状压 DP记忆化搜索半平面交方向判定直线相交鞋带公式

凸包2

题目描述

A 和 B 玩一个游戏:

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

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

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

输入格式

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

接下来 kk 行按逆时针顺序给出多边形的顶点坐标 Xi,YiX_i,Y_i。

第 k+2k+2 行输入一个正整数 nn,表示直线的数目。

接下来 nn 行,每行 44 个整数 Xi,1,Yi,1,Xi,2,Yi,2X_{i,1},Y_{i,1},X_{i,2},Y_{i,2},表示直线上的不重合两点的坐标。

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

输出格式

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

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

40000.00000 

数据规模与约定

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

对于 100%100\% 的数据 n≤9n\le 9,k≤20k\le 20。

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

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

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