题解 CF1216C 【White Sheet】

梦里梦外; 2023-06-01 12:43 30阅读 0赞

虽然也很水，但这道还是比前两道难多了...

--------------------

题目大意：给你三个位于同一平面直角坐标系的矩形，询问你后两个是否完全覆盖了前一个

首先，最直观的想法应该是，把第一个矩形内部每个整数点检查一下，看看是否位于其他两个矩形的内部

但是一看数据范围，哇，$10^6$，点最多就有$\{10\}^\{12\}$个，直接爆炸，好走不送

我们只能换思路了。。。

考虑两个矩形超出那个矩形的部分没有任何用处，直接砍掉

这样我们就只用考虑这个矩阵内部了

可以看出，覆盖也可以说是矩形切掉了位置与盖在上面的矩形相同的且相当于上面的矩形大小的一块，但这样做还是太过麻烦，因为有时会变成下图这样：

![1685943-20190921222613955-493866925.png][]

倘若这个矩形没有彻底覆盖大矩形的一条边（这个表达其实有问题，但大家应该能够理解），那么这个矩形的覆盖是对覆盖整个大矩形是没有贡献的，因为剪裁后不能使得大矩形的长短缩小

所以我们只需要将大矩形切掉能彻底覆盖大矩形一条边的矩形即可，。

这个是实现应该很简单，毕竟直接缩小大矩形长短即可，最后判断大矩形是否被切没了就能判断是否能被覆盖了

P.S. 记得判断小矩形是否被切完了，切完就不要执行操作了（感谢 @YiShen 提供hack数据）

代码如下：

#include<cstdio>
    
    inline int read(){
    	int r=0,f=1;
    	char c=getchar();
    	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    	while(c>='0'&&c<='9')r=(r<<1)+(r<<3)+c-'0',c=getchar();
    	return r*f;
    }
    
    int x[2],y[2],b_x[2],b_y[2];
    
    inline int min(int a,int b){
    	return a<b?a:b;
    }
    
    inline int max(int a,int b){
    	return a>b?a:b;
    }
    
    int main(){
    	x[0]=read(),y[0]=read();
    	x[1]=read(),y[1]=read();
    	for(int i=1;i<=2;i++){
    		b_x[0]=max(read(),x[0]),b_y[0]=max(read(),y[0]);//超出大矩形，砍掉
    		b_x[1]=min(read(),x[1]),b_y[1]=min(read(),y[1]);//超出大矩形，砍掉
    		for(int j=0;j<=1;j++)//先看左边和下面，再看右边和上面 
    			if(b_x[j]==x[j]&&b_y[j]==y[j]){//倘若连顶点都没覆盖，更别说整条边了 
    				if(b_x[j^1]==x[j^1])y[j]=b_y[j^1];//看看该边是否被覆盖，若是，将大矩形切去这一段 
    				if(b_y[j^1]==y[j^1])x[j]=b_x[j^1];//看看该边是否被覆盖，若是，将大矩形切去这一段
    			}
    	}
    	if(x[0]==x[1]&&y[0]==y[1])printf("NO");
    	else printf("YES");
    	return 0;
    }

倘若无法理解此处的异或运算（其实就是相对的两个顶点（左下和右上）），建议手模或者调试走一遍

转载于:https://www.cnblogs.com/wyzwyz/p/11565009.html

[1685943-20190921222613955-493866925.png]: /images/20230601/4c69f59b00f248de837ebcbbd51e5c2b.png