Codeforces Round #587 C. White Sheet（思维+计算几何）

•题意

先给一个白矩阵，再两个黑矩阵

如果两个黑矩阵能把白矩阵包含，则输出NO

否则输出YES

•思路

计算几何题还是思维题呢?

想起了上初中高中做几何求面积的题

这个就类似于那样

包含的话分两种情况讨论，其他的不包含

①白矩形在一个黑矩形内部

　　这种情况直接判断边界就可以

②白矩形在两个黑矩形组合的图形内部

首先这个情况的前提是两个黑矩形必须能连接起来

白矩形和两个黑矩形分别会有重合，重合的地方可能会在此重合，

　　例如白矩形(1 1 4 2) 黑1矩形(1 0 3 4) 黑2矩形(2 0 5 3)

　　　　

被黑1黑2矩阵联合包含，与黑1相交面积是粉色区域，与黑2相交面积是绿色区域

但是粉绿色区域的多算的，白矩阵面积=粉色面积+绿色面积-粉绿面积

•代码

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 struct node

 {

     ll xl,yl,x2,y2;

 }a[],p;

 bool CH(node x,node y )//重合

 {

     if(x.xl>=y.xl&&x.x2<=y.x2&&x.yl>=y.yl&&x.y2<=y.y2)

         return true;

     return false;

 }

 ll XJ(node a,node b)//相交

 {

     ll cx1=max(a.xl,b.xl);

     ll cy1=max(a.yl,b.yl);

     ll cx2=min(a.x2,b.x2);

     ll cy2=min(a.y2,b.y2);

     if(cx1>cx2||cy1>cy2)//不相交

     p=node{cx1,cy1,cx2,cy2};//相交矩形

     return (cx2-cx1)*(cy2-cy1);//相交面积

 }

 ///包括NO 不包括YES

 int main()

 {

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

         cin>>a[i].xl>>a[i].yl>>a[i].x2>>a[i].y2;

     if(CH(a[],a[])||CH(a[],a[]))///重合在内部

     {

         puts("NO");

         return ;

     }

     if(XJ(a[],a[])<) ///2 3不相交

     {

         puts("YES");

         return ;

     }

     if(XJ(a[],a[])>=) ///2 3相交

     {

         ll s1=XJ(a[],a[]);

         node p1=p;

         ll s2=XJ(a[],a[]);

         node p2=p;

         ll s=(a[].y2-a[].yl)*(a[].x2-a[].xl);

         s+=max(1ll*,XJ(p1,p2));///重合处会多算

         if(s1+s2==s)

         {

             puts("NO");

             return ;

         }

         else

         {

             puts("YES");

             return ;

         }

     }

 }

 /**

 1 1 4 2

 1 0 3 4

 2 0 5 3

 */

巴特西

Codeforces Round #587 C. White Sheet（思维+计算几何）

•题意

•思路

•代码

最新文章

热门文章