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相交面积是绿色区域

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

•代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 struct node
 5 {
 6     ll xl,yl,x2,y2;
 7 }a[4],p;
 8 
 9 bool CH(node x,node y )//重合
10 {
11     if(x.xl>=y.xl&&x.x2<=y.x2&&x.yl>=y.yl&&x.y2<=y.y2)
12         return true;
13     return false;
14 }
15 ll XJ(node a,node b)//相交
16 {
17     ll cx1=max(a.xl,b.xl); 
18     ll cy1=max(a.yl,b.yl); 
19     ll cx2=min(a.x2,b.x2); 
20     ll cy2=min(a.y2,b.y2); 
21     if(cx1>cx2||cy1>cy2)//不相交
22 
23     p=node{cx1,cy1,cx2,cy2};//相交矩形
24     return (cx2-cx1)*(cy2-cy1);//相交面积
25 }
26 
27 ///包括NO 不包括YES
28 int main()
29 {
30     for(ll i=1;i<=3;i++)
31         cin>>a[i].xl>>a[i].yl>>a[i].x2>>a[i].y2;
32 
33     if(CH(a[1],a[2])||CH(a[1],a[3]))///重合在内部
34     {
35         puts("NO");
36         return 0;
37     }
38 
39     if(XJ(a[2],a[3])<0) ///2 3不相交
40     {
41         puts("YES");
42         return 0;
43     }
44 
45     if(XJ(a[2],a[3])>=0) ///2 3相交
46     {
47         ll s1=XJ(a[1],a[2]);
48         node p1=p;
49         ll s2=XJ(a[1],a[3]);
50         node p2=p;
51         ll s=(a[1].y2-a[1].yl)*(a[1].x2-a[1].xl);
52         s+=max(1ll*0,XJ(p1,p2));///重合处会多算
53 
54         if(s1+s2==s)
55         {
56             puts("NO");
57             return 0;
58         }
59         else
60         {
61             puts("YES");
62             return 0;
63         }
64     }
65 }
66 
67 /**
68 1 1 4 2
69 1 0 3 4
70 2 0 5 3
71 */

View Code