更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解
原题链接： 202303-1 田地丈量
时间限制： 1.0s
内存限制： 512.0MB
问题描述
西西艾弗岛上散落着 n n n 块田地。每块田地可视为平面直角坐标系下的一块矩形区域，由左下角坐标 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 和右上角坐标 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 唯一确定，且满足 x 1 < x 2 x_1 < x_2 x1<x2、 y 1 < y 2 y_1 < y_2 y1<y2。这 n n n 块田地中，任意两块的交集面积均为 0 0 0，仅边界处可能有所重叠。
最近，顿顿想要在南山脚下开垦出一块面积为 a × b a \times b a×b 矩形田地，其左下角坐标为 ( 0 , 0 ) (0, 0) (0,0)、右上角坐标为 ( a , b ) (a, b) (a,b)。试计算顿顿选定区域内已经存在的田地面积。
输入格式
从标准输入读入数据。
输入共 n + 1 n+1 n+1 行。
输入的第一行包含空格分隔的三个正整数 n n n、 a a a 和 b b b，分别表示西西艾弗岛上田地块数和顿顿选定区域的右上角坐标。
接下来 n n n 行，每行包含空格分隔的四个整数 x 1 x_1 x1、 y 1 y_1 y1、 x 2 x_2 x2 和 y 2 y_2 y2，表示一块田地的位置。
输出格式
输出到标准输出。
输出一个整数，表示顿顿选定区域内的田地面积。
样例输入
4 10 10
0 0 5 5
5 -2 15 3
8 8 15 15
-2 10 3 15
样例输出
44
样例解释
如图所示，选定区域内田地（绿色区域）面积为 44 44 44。
子任务
全部的测试数据满足 n ≤ 100 n \le 100 n≤100，且所有输入坐标的绝对值均不超过 1 0 4 10^4 104。
题解
对于每个给定的矩形 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2)，如果它和需要开垦的田地有交集，则相交的矩形应为 ( max { x 1 , 0 } , max { y 1 , 0 } ) , ( min { x 2 , a } , min { y 2 , b } ) (\max\{x_1,0\},\max\{y_1,0\}),(\min\{x_2,a\},\min\{y_2,b\}) (max{x1,0},max{y1,0}),(min{x2,a},min{y2,b})。
排除掉不相交的矩形，即 max { x 1 , 0 } > min { x 2 , a } \max\{x_1,0\}>\min\{x_2,a\} max{x1,0}>min{x2,a} 或 max { y 1 , 0 } > min { y 2 , b } \max\{y_1,0\}>\min\{y_2,b\} max{y1,0}>min{y2,b}，直接计算矩形面积即可。
时间复杂度： O ( n ) \mathcal{O}(n) O(n)。
参考代码（0ms，2.964MB）
/*
Created by Pujx on 2024/3/19.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) void(0)
#endif
const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }
int a[N];
int n, m, t, k, q;
void work() {
int a, b;
cin >> n >> a >> b;
int ans = 0;
while (n--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1 = max(x1, 0), y1 = max(y1, 0);
x2 = min(x2, a), y2 = min(y2, b);
if (x1 > x2 || y1 > y2) continue;
ans += (x2 - x1) * (y2 - y1);
}
cout << ans << endl;
}
signed main() {
#ifdef LOCAL
freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int Case = 1;
//cin >> Case;
while (Case--) work();
return 0;
}
/*
_____ _ _ _ __ __
| _ \ | | | | | | \ \ / /
| |_| | | | | | | | \ \/ /
| ___/ | | | | _ | | } {
| | | |_| | | |_| | / /\ \
|_| \_____/ \_____/ /_/ \_\
*/
关于代码的亿点点说明：
- 代码的主体部分位于
void work()函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ...是用来开启 O2、O3 等优化加快代码速度。- 中间一大堆
#define ...是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h"头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义DEBUG宏），在程序中如果看到dbg(...)是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);这三句话是用于解除流同步，加快输入cin输出cout速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用scanf和printf，但使用了这句话后，cin和scanf、cout和printf不能混用。- 将
main函数和work函数分开写纯属个人习惯，主要是为了多组数据。
