bzoj#P3778. 共鸣

共鸣

题目描述

GHQ 通过在 24 区引起基因组共鸣,从而引发了第二次失落的圣诞。

24 区的地图可以视为一个二维平面。GHQ 在 24 区布置了 mm 架发射塔,而葬仪社也建立了 nn 个据点。要阻止共鸣,需要顺次连接一些据点,连接的两个据点之间会形成屏障。所有屏障应构成一个多边形,称之为干扰场。干扰场的面积越大,起到的干扰效果就越强。

但是并非所有的连接方式都是有效的。其一,任意两块屏障不能在据点之外的位置相交;其二,干扰场中的任意一个位置都应该可以直接看到构成干扰场的所有据点。所谓直接看到是指视线不会穿过任意一块屏障。

更重要的一点是,干扰场内不能存在有 GHQ 布置的发射塔,而且屏障也不能穿过发射塔。如果这个条件不满足,干扰场根本无法发挥作用。

葬仪社需要设计一个构成干扰场的方案,使得干扰场的面积最大。请你协助他们。

输入格式

输入文件的第一行包含两个整数 nnmm,分别代表葬仪社的据点个数,以及 GHQ 设立的发射塔架数。

接下来 nn 行,每行包含一个坐标,表示葬仪社的一个据点的位置。

接下来 mm 行,每行包含一个坐标,表示 GHQ 布置的一架发射塔的位置。

坐标的每一维皆为绝对值不超过 10310^3 的整数。输入的任意两个坐标不相同。

输出格式

第一行输出一个非负实数,表示干扰场的最大面积。保留两位小数。

3 1
0 0
3 0
0 4
1 1
0.00
4 1
0 0
3 0
3 3
0 3
1 0
4.50

样例解释

对于第一个样例,唯一的正面积干扰场是由据点 1,2,31,2,3 构成的,但是发射塔 11 在这个干扰场内部,所以不存在合法的正面积干扰场。 注意第三行的空行。

数据规模与约定

对于 100%100\% 的数据,n100n \le 100m100m \le 100