[NWERC2007]飞行安全

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file flightsafety.in Output file flightsafety.out

【题目描述】

在规划客机航线时安全是一个重要的问题。首先,显然应当采取任何可能的措施来确保旅途平安无事。但即使那样,也应当时刻为最坏的情况做好准备,设法确保即使事故发生,乘客的生还概率也尽可能高。

当飞机在水面迫降时,到最近陆地的距离是一个关键因素。一般而言,在开阔水面上离岸边越远,生还的希望就越小。因此,航班一个重要的安全系数就是航线上任意位置到最近陆地的距离。你的任务是写一个程序,对给定的航线计算这个距离。

为了简化问题,我们将世界视作一个二维平面而非球体。我们将陆地视作多边形,将航线视作由直线段连接的一系列路径点。航线的起点和终点总是严格地处于一块陆地内部,但中间的路径点可能在水面上。陆地的边界不会自交,陆地之间也不会相交。

【输入格式】

第一行有一个正整数,代表数据组数(<20)。每组数据格式如下:

第一行包含两个整数C(1<=C<=20)和N(2<=N<=20),C是陆地数量,N是路径点数量。

接下来有N行,每行两个整数X,Y,按照航线顺序给出了N个路径点的坐标。

接下来是对于C块陆地的描述。格式如下:

第一行有一个整数M(3<=M<=30),代表顶点数。接下来M行每行有一对整数X,Y,按照顺时针或逆时针顺序给出了M个顶点的坐标。

所有坐标范围[-10000,10000]。

【输出格式】

对每组数据输出一行一个实数,代表航线离最近陆地最远处到最近陆地的距离。精确到小数点后六位。

当且仅当你的输出和标准输出之差的绝对值不超过10^-3时我们认为你的答案正确。

【样例输入】

2

1 2

-9 -6

5 1

3

0 16

-16 -12

17 -6

2 3

12 4

16 17

3 9

4

1 0

4 19

19 14

6 12

3

10 10

5 3

18 2

【样例输出】

0.000000

2.942685

【提示】

第二组样例如图。最远点用方块标记。

【来源】

NWERC 2007 Problem F Flight Safety