| 题目名称 | 2776. [poj3608]岛屿间的桥梁 |
|---|---|
| 输入输出 | poj3608.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Shirry
于2017-08-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 Shirry |
100 | 0.002 s | 0.60 MiB | C++ |
| 关于 岛屿间的桥梁 的近10条评论(全部评论) |
|---|
【题目描述】
数千年前，有一个位于太平洋中部的小王国。王国的领土是两个分开的岛屿。
受海流的影响，两岛的形状都变成凸多边形。
国王要建立一座连接这两个岛屿的桥梁。为了最大限度地降低成本，国王想让你找到这两个岛屿边界之间的最小距离。
【输入格式】
有多组测试数据。
每个测试数据从两个整数N，M开始。（3≤N，M ≤10000）
之后N行中的每一行都包含一个坐标，其描述了一个凸多边形顶点的位置。
之后M行中的每一行都包含一个坐标，其描述了另一个凸多边形顶点的位置。
N=M=0表示输入结束。
坐标在[-10000，10000]范围内。
【输出格式】
输出对于每个测试数据的答案。
0.001以内的误差是可以接受的。
【样例输入】
4 4
0.00000 0.00000
0.00000 1.00000
1.00000 1.00000
1.00000 0.00000
2.00000 0.00000
2.00000 1.00000
3.00000 1.00000
3.00000 0.00000
0 0
【样例输出】
1.00000
【提示】
在此键入。
【来源】
POJ创始人每月比赛 - 2008.06.29，雷涛