共鸣
时间限制:20s 空间限制:512MB
题目描述
GHQ通过在24区引起基因组共鸣,从而引发了第二次失落的圣诞。
24区的地图可以视为一个二维平面。GHQ在24区布置了 架发射塔,而葬仪社也建立了 个据点。要阻止共鸣,需要顺次连接一些据点,连接的两个据点之间会形成屏障。所有屏障应构成一个多边形,称之为干扰场。干扰场的面积越大,起到的干扰效果就越强。
但是并非所有的连接方式都是有效的。其一,任意两块屏障不能在据点之外的位置相交;其二,干扰场中的任意一个位置都应该可以直接看到构成干扰场的所有据点。所谓直接看到是指视线不会穿过任意一块屏障。
更重要的一点是,干扰场内不能存在有GHQ布置的发射塔,而且屏障也不能穿过发射塔。如果这个条件不满足,干扰场根本无法发挥作用。
葬仪社需要设计一个构成干扰场的方案,使得干扰场的面积最大。请你协助他们。
输入格式
输入文件的第一行包含两个整数 和 ,分别代表葬仪社的据点个数,以及GHQ设立的发射塔架数。
接下来 行,每行包含一个坐标,表示葬仪社的一个据点的位置。
接下来 行,每行包含一个坐标,表示GHQ布置的一架发射塔的位置。
坐标的每一维皆为绝对值不超过1000的整数。输入的任意两个坐标不相同。
输出格式
第一行输出一个非负实数,表示干扰场的最大面积。保留两位小数。
样例输入
【样例输入1】 3 1 0 0 3 0 0 4 1 1 【样例输入2】 4 1 0 0 3 0 3 3 0 3 1 0
样例输出
【样例输出1】 0.00 【样例1解释】 唯一的正面积干扰场是由据点1、2、3构成的,但是发射塔1在这个干扰场内部,所以不存在合法的正面积干扰场。 注意第三行的空行。 【样例输出2】 4.50
提示
N<=100,M<=100
题目来源
没有写明来源