5838: BZOJ1838:凸包2

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: