/ Vijos / 题库 /

家园转移计划

家园转移计划

背景

大约一年前,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

信息

ID
1402
难度
8
分类
动态规划 点击显示
标签
(无)
递交数
46
已通过
7
通过率
15%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

SQ CLASS公开编程竞赛2008