Blocked Billboard II题解--模拟到崩溃的模拟

前言

比赛真的状态不好（腐了一小会），导致差点爆0。

这个题解真的是在非常非常专注下写出来的，要不然真的心态崩。

题目

题目描述

奶牛Bassie想要覆盖一大块广告牌，她在之前已经覆盖了一小部分广告牌（但覆盖的这块面积不一定在广告牌上）

现在她要取一块足够大的布来将剩下的部分覆盖，问至少要多大的矩形的布才能覆盖剩下的广告牌。

输入

输入共两行。

第一行四个整数，l1,r1,l2,r1，描述广告牌左下和右上两个坐标(l1,r1)和(l2,r2)。

第二行四个整数，x1,y1,x2,y2，描述覆盖的位置的左下和右上两个坐标(x1,y1)和(x2,y2)。

所有数值都在-1000~1000范围内。

输出

一行一个整数，表示需要的最小的矩形的布。

样例输入

2 1 7 4
5 -1 10 3

样例输出

思路

第一眼给我们的印象：模拟、枚举。

可是单单这样没头没脑没方向没想法没目标想的话，是不是有点复杂？

所以思考一下，淡定一点，我们可以看出：

只有在四周长条状覆盖才有用。

比如下图：

其他覆盖例如在中间一小块，四角都没有任何卵用作用……咳咳。

而除了这样覆盖，就只有剩下两种情况：原来的面积或者0

思路来了。那就是代码实现的问题了。

代码实现

没错还是这幅图。枚举了四种中的一种情况——上。

那么我们可以看出符合上的条件是：x1 > l1 && y1 <= r1 && x2 >= l2 && y2 >= r2 && x1 < l2。

x1 > l1 && x1 < l2：这一条线决定了覆盖的范围，但不能与原本正方形的两条边重合（重合即为0）

x2 >= l2 && y2 >= r2 && y1 <= r1：若不满足则覆盖面积必定为四角类型（左上，左下，右上，右下），但几条线可以重合，并不影响考虑的情况。

其他的3种情况就以此类推。

主要是草稿纸上画图，再分别标出8个数字在图上对应的位置，推理一下就可以知道这个长条区域所需要的条件。

最终贴上代码：

#include<cstdio>
using namespace std;
int l1, r1, l2, r2;
int x1, y1, x2, y2;
int sum, a, b, c, d;
int abs(int x)
{
	if(x < 0)
		return -x;
	return x;
}
int main() {
    scanf("%d%d%d%d%d%d%d%d", &l1, &r1, &l2, &r2, &x1, &y1, &x2, &y2);
    if(x1 <= l1 && y1 <= r1 && x2 >= l2 && y2 >= r2)
    	printf("%d",0);//0
	else if(x1 > l1 && y1 <= r1 && x2 >= l2 && y2 >= r2 && x1 < l2)
		printf("%d",abs(r2 - r1) * abs(x1 - l1));//up
	else if(y2 < r2 && r2 > r1 && x2 >= l2 && x1 <= l1 && y1 <= r1)
		printf("%d",abs(l2 - l1) * abs(r2 - y2));//left
	else if(x2 > l1 && x2 < l2 && y2 >= r2 && x1 <= l1 && y1 <= r1)
		printf("%d",abs(r2 - r1) * abs(l2 - x2));//down
	else if(y1 < r2 && y1 > r1 && x1 <= l1 && x2 >= l2 && y2 >= r2)
		printf("%d",abs(l2 - l1) * abs(y1 - r1));//right
	else
		printf("%d",abs(l2 - l1) * abs(r2 - r1));//all
}

备注：调用cmath库不能使用“y1”变量╮(╯▽╰)╭，但是我又怕粗心导致里面有负数，如果确定的情况下可不用abs。

题目倒是挺水，就是不知道你有没有耐心

巴特西

Blocked Billboard II题解--模拟到崩溃的模拟

前言

题目

题目描述

输入

输出

样例输入

样例输出

思路

代码实现

最新文章

热门文章