过度种植

题目

给N个矩阵中每个矩阵的左上角和右下角 求出这N个矩阵所覆盖的面积

输入输出格式

输入格式

第一行,一个整数N。 (1 <= N <= 10)。

接下来有N行,每行描述一个矩形的信息,分别是矩形的x1、y1、x2、y2。

其中 -10^4 <= x1,y1,x2,y2 <= 10^4。

输出格式

一个整数,被N个矩形覆盖的区域的面积。

输入输出样例

输入样例

2

0 5 4 1

2 4 6 2

输出样例

20

思路

利用递归函数 自己调用自己 对于每个矩阵进行切割

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define Max(x, y) (x >= y ? x : y)
#define Min(x, y) (x <= y ? x : y)
#define F(i, x, y) for(register int i=x; i<=y; i++)
#define R(i, x, y) for(register int i=x; i>=y; i--)
using namespace std;
inline void in(int &x)
{
static int ch; static bool flag;
for(flag=false, ch=getchar(); ch<'0'||ch>'9'; ch=getchar()) flag |= ch=='-';
for(x=0; isdigit(ch); ch=getchar()) x = (x<<1) + (x<<3) + ch - '0';
x = flag ? -x : x;
}
int n, ans;
int x1[20], x2[20], Y1[20], y2[20];
void solve(int left, int right, int high, int low, int k)
{
if (left>right||high<low) return ;
while(k>0 && (left>=x2[k]||right<=x1[k]||high<=y2[k]||low>=Y1[k])) k--;
if (!k) {ans += (right-left)*(high-low); return ;}
if (left<x1[k]){solve(left,x1[k],high,low,k-1); left=x1[k];}
if (right>x2[k]){solve(x2[k],right,high,low,k-1); right=x2[k];}
if (high>Y1[k]){solve(left,right,high,Y1[k],k-1); high=Y1[k];}
if (low<y2[k]){solve(left,right,y2[k],low,k-1); low=y2[k];}
}
inline int work()
{
in(n); F(i, 1, n) in(x1[i]), in(Y1[i]), in(x2[i]), in(y2[i]);
F(i, 1, n) solve(x1[i], x2[i], Y1[i], y2[i], i-1);
printf("%d\n", ans);
return 0;
}
int TAT = work();
int main() {;}