• [1640] 多边形的公共部分

  • 时间限制: 5000 ms　内存限制: 65535 K
  • 问题描述



  • 给定两个简单多边形,你的任务是判断二者是否有面积非空的公共部分。如下图,(a)中的两个 

    矩形只有一条公共线段,没有公共面积。 



    在本题中,简单多边形是指不自交(也不会接触自身)、不含重复顶点并且相邻边不共线的多
边形。 
    注意:本题并不复杂,但有很多看上去正确的算法实际上暗藏缺陷,请仔细考虑各种情况。



  • 输入
  • 输入包含不超过 100 组数据。每组数据包含两行,每个多边形占一行。多边形的格式是:第一 个整数 n 表示顶点的个数 (3<=n<=100),接下来是 n 对整数(x,y) (-1000<=x,y<=1000),即多边 形的各个顶点,按照逆时针顺序排列。
  • 输出
  • 对于每组数据,如果有非空的公共部分,输出"Yes",否则输出"No"。
  • 样例输入
  • 4 0 0 2 0 2 2 0 2
4 2 0 4 0 4 2 2 2
4 0 0 2 0 2 2 0 2
4 1 0 3 0 3 2 1 2
  • 样例输出
  • Case 1: No
Case 2: Yes
  • 提示
  • 无
  • 来源
  • 第十一届“蓝狐网络杯”湖南省大学生计算机程序设计竞赛
  • 操作

显示春菜