OI题库

【题目描述】

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

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

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

【输入格式】

第一行有一个正整数，代表数据组数（<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