No submission language available for this problem.

题目描述

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