logo AlgoBeat OnlineJudge
登录 注册

#101838. [BZOJ 1838] 凸包2

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

A 和 B 玩一个游戏:

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

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

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

输入格式

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

接下来 行按逆时针顺序给出多边形的顶点坐标

行输入一个正整数 ,表示直线的数目。

接下来 行,每行 个整数 ,表示直线上的不重合两点的坐标。

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

输出格式

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

样例

样例输入 #1

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

样例输出 #1

40000.00000 

数据范围与提示

对于 的数据

对于 的数据

输入数据保证所有给出的坐标值都是绝对值不超过 的整数,

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

精度取 足够。