当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
4860：新海岛计划
题目描述
在填海计划完成第一步之后，你突然发现城市的陆地空间还是不足，于是开始筹划填建一座新的海岛。
经过简单的实地评估，你发现你所能规划的区域是一个W*H的矩形区域，在其中，已经存在一些建好的岛屿，它们的形状都是凸多边形，标准的凸包形状。
你需要新建的海岛形状也已经给出，也是一个凸多边形，你可以平移这个形状将其建立在矩形区域内任何空白的不与其他海岛相交的位置，但不能伸缩或旋转。你想知道这个计划是否可行，也就是说，是否存在足够的空白区间能够建立这个新岛。注意，已存在的海岛可能相交，但是新建的海岛只能有点或边的重合，不能与已存在的海岛相交。
经过简单的实地评估，你发现你所能规划的区域是一个W*H的矩形区域，在其中，已经存在一些建好的岛屿，它们的形状都是凸多边形，标准的凸包形状。
你需要新建的海岛形状也已经给出，也是一个凸多边形，你可以平移这个形状将其建立在矩形区域内任何空白的不与其他海岛相交的位置，但不能伸缩或旋转。你想知道这个计划是否可行，也就是说，是否存在足够的空白区间能够建立这个新岛。注意，已存在的海岛可能相交，但是新建的海岛只能有点或边的重合，不能与已存在的海岛相交。
输入解释
输入第一行为T，表示有T组测试数据。
每组数据以三个整数W，H，N开始，表示大的矩形区域以 (0,0) 和 (W,H) 作为左下和右上的顶点。接下来的N+1行，每行以一个整数M开始，接着M对整数 (Xi, Yi)，以逆时针顺序给出一个凸多边形。其中，第一个表示计划新建的海岛。
[Technical Specification]
1. 1 <= T <= 1000
2. 0 <= N <= 20
3. 3 <= M <= 20
4. 0 <= W, H, Xi, Yi <= 10000
每组数据以三个整数W，H，N开始，表示大的矩形区域以 (0,0) 和 (W,H) 作为左下和右上的顶点。接下来的N+1行，每行以一个整数M开始，接着M对整数 (Xi, Yi)，以逆时针顺序给出一个凸多边形。其中，第一个表示计划新建的海岛。
[Technical Specification]
1. 1 <= T <= 1000
2. 0 <= N <= 20
3. 3 <= M <= 20
4. 0 <= W, H, Xi, Yi <= 10000
输出解释
对每组数据，先输出为第几组数据，如果方案可行，输出“Yes”，否则输出“No”。
输入样例
2 3 3 1 3 0 0 2 0 0 2 4 1 1 3 1 3 3 1 3 3 3 1 3 0 0 2 0 0 2 4 0 0 2 0 2 2 0 2
输出样例
Case 1: Yes Case 2: No
提示
样例1示意图：样例2示意图：
来自杭电HDUOJ的附加信息
| Author | Isea@WHU |
| Recommend |
最后修改于 2020-10-25T23:17:31+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 2000/1000MS(Java/Others) | 32768/32768K(Java/Others) |
登陆或注册以提交代码