新海岛计划

Accepts: 0
Submissions: 2
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
在填海计划完成第一步之后,你突然发现城市的陆地空间还是不足,于是开始筹划填建一座新的海岛。 经过简单的实地评估,你发现你所能规划的区域是一个W*H的矩形区域,在其中,已经存在一些建好的岛屿,它们的形状都是凸多边形,标准的凸包形状。 你需要新建的海岛形状也已经给出,也是一个凸多边形,你可以平移这个形状将其建立在矩形区域内任何空白的不与其他海岛相交的位置,但不能伸缩或旋转。你想知道这个计划是否可行,也就是说,是否存在足够的空白区间能够建立这个新岛。注意,已存在的海岛可能相交,但是新建的海岛只能有点或边的重合,不能与已存在的海岛相交。
Input
输入第一行为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
Output
对每组数据,先输出为第几组数据,如果方案可行,输出“Yes”,否则输出“No”。
Sample Input
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
Sample Output
Case 1: Yes
Case 2: No
Hint
样例1示意图: [center][img]../../data/images/C518-1004-1.jpg[/img][/center] 样例2示意图: [center][img]../../data/images/C518-1004-2.jpg[/img][/center]