CodeForces 1216C（假的计算几何+扫描线）

•题意

　　给你三个矩形，依次编号为 1,2,3；

　　判断矩形1 是否被矩形2 和矩形3 完全覆盖；

　　如果没有完全覆盖，输出 "YES"，反之，输出 "NO"；

•题解

　　我是用扫描线做的；

　　首先，定义如下数据结构：
 struct Data

 {

     int x;

     int y1,y2;

     int f;

     int id;

     bool operator < (const Data& obj)const

     {

         return x < obj.x;

     }

 }line[],white[];
　　先扫描竖直边；

　　将这 3 个矩形的左右边分别存入上述数据结构中；

　　并保存矩形1 的左右边；
 int num=;

 for(int i=;i <= ;++i)

 {

     int x1,y1;

     int x2,y2;

     scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

     if(i == )

     {

         white[]={x1,y1,y2,,i};///f=1表示该边为当前矩形的左边，f=-1表示该边为当前矩形的右边

         white[]={x2,y1,y2,-,i};///保存矩阵1的两个竖直边

     }

     line[++num]={x1,y1,y2,,i};///保存矩阵的竖直边

     line[++num]={x2,y1,y2,-,i};

 }
　　保存好边的信息后，按照 x 升序排列；

　　接下来就是判断矩形1 的竖直边是否被矩形2，3 完全覆盖；

　　但是，仅仅判断竖直边是否被完全覆盖是不够的，还需要扫描水平边；

　　原因的话，可以模拟一下如下样例：
　　这样的话，就得需要保存矩形的上下边，并再次扫描一遍；

　　只有当矩形1 的竖直边和水平边都分别被矩形2，3 完全覆盖时，才能说明矩形1 被矩形2，3 完全覆盖；

•Code

　　CodeForces1216C.cpp

•Wa过的样例
　　此样例很明确的说明了 Code 中第 49~50 行的判断语句的放置位置以及如何确定判断条件；

　　还有一个就是上述题解中的样例，明确的说明了为什么要扫描两次；

巴特西

CodeForces 1216C（假的计算几何+扫描线）

•题意

•题解

•Code

•Wa过的样例

最新文章

热门文章