家园转移计划
背景
大约一年前,royZhang介绍给liuichou一种网页游戏叫做“OGame”。liuichou又在SQ CLASS中推行了这个游戏。自此,“OGame”在SQ CLASS中风靡到了现在。
描述
SQ CLASS在“OGame”中的联盟在有气吞山河之势,并划有势力圈。这个势力圈是以殖民星直线连接起来的。不良企图者入侵近来,在势力圈内占领了几个行星。SQ CLASS联盟在商讨后决定,利用原来的一些殖民星划出一个安全区,把家园和资源搬到安全区中进行生产,以防被掠夺。安全区是势力圈内殖民星连接起来的,中不得有被入侵者占领的行星。为了在迁移过程中也不受攻击,安全区中任意两星的连线必须全部在安全区内或安全区连线上。SQ CLASS不希望安全区被分隔开,所以围成安全区的任意两段连线除在行星外不能相交。当然他们也需要一个面积最大的安全区。请用编写程序帮助他们圈出安全区的面积。
注意:围成安全区的连线是允许经过被占领行星的。
格式
输入格式
第一行是一个整数n(1<=n<=100),表示殖民星的数目。接下来又n行,每行两个整数Xi, Yi (|Xi|<=10000, |Yi|<=10000), 按逆时针顺序给出每个殖民星所在的坐标,这些殖民星顺次连成一个凸多边形(该多边形只是形状是凸的,即某些殖民星可能会落在多边形边上)。然后是一个整数m(1<=m<=100),表示被占领行星的个数,跟着m行,每行两个整数Pi,Qi(|Pi|<=10000,|Qi|<=10000),即被占领行星的坐标,该坐标点可能落在势力圈的边上或外面,但不会占领原来构成势力圈的殖民星。
输出格式
输出文件只有一行,为安全区的最大面积,答案保留两位小数。如果不可能围成安全区,则输出“LOSE”(大写,不包括引号)。
样例1
样例输入1
4
4 4
-4 4
-4 -4
4 -4
2
0 1
3 3
样例输出1
32.00
限制
1 second
来源
SQ CLASS公开编程竞赛2008——Problem B
Source: liuichou, royZhang