/ Vijos / 题库 /

冰冻之海

冰冻之海

背景

波罗的海,位于东北欧,围绕波罗的海的国家与地区包括斯堪地拉维亚半岛、中东欧大陆部分和丹麦。波罗的海北纬54度起向东北延伸到北极圈附近...波罗的海的海岸线十分曲折,海中岛屿林立,瑞典首都斯德哥尔摩、芬兰首都赫尔辛基、拉脱维亚首都里加等都是波罗的海沿岸的名城。

不仅如此...波罗的海还是世界上盐度最低的海域。这是因为海区闭塞;周围河川径流总量丰富。波罗的海的海水含盐度只有7-8‰,大大低于全世界海水平均含盐度(35‰),而各个海湾的盐度更低,只有2‰左右。

北部和东部海域每年通常有一段不利于航行的冰封期。鲱鱼、鳕鱼、鲽鱼是这里的特产。

波罗的海的平均深度只有55米,也正式因为如此...又浅又淡的海水容易结冰。因此它又被称为."冰冻之海" ...

也可以参考这里...

描述

输入数据的第一行是一个不大于1000的数字n,标识出n块冰块。

紧接着每一行描述一个冰块..每一个冰块都是一个多边形,第一个数字是边数m。

然后按顺时针顺序描述每个顶点的坐标....
输入数据的最后两行分别描述当前船只的坐标以及目标地点的位置...

请计算出从出发点到目标地点不碰到冰块的最短距离...
你可以假定所有的数据都是非负整数...

样例1

样例输入1

4
4 1 1 1 2 2 2 2 1
4 1 3 1 4 2 4 2 3
4 3 1 3 2 4 2 4 1
4 3 3 3 4 4 4 4 3 
0 0
5 5

样例输出1

7.30

提示

0<=n<=100,1<=m<=36..输出结果保留两位小数...
船比较小...所以可以从两块浮冰的夹缝中走出...#...
不会出现一开始就在冰块内部的情况..不过我们可以暂时假定所有的冰块都是凸多边形..
不过...其他情况都会出现...别大意呀..> <

信息

ID
1682
难度
9
分类
计算几何 | 图结构 | 最短路 点击显示
标签
递交数
69
已通过
4
通过率
6%
被复制
3
上传者