913 字
5 分钟
P5490 【模板】扫描线 & 矩形面积并

P5490 【模板】扫描线 & 矩形面积并#

题目描述#

求 nn 个四边平行于坐标轴的矩形的面积并。

输入格式#

第一行一个正整数 nn。

接下来 nn 行每行四个非负整数 x1,y1,x2,y2x_1, y_1, x_2, y_2,表示一个矩形的四个端点坐标为 (x1,y1),(x1,y2),(x2,y2),(x2,y1)(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)。

输出格式#

一行一个正整数,表示 nn 个矩形的并集覆盖的总面积。

输入输出样例 #1#

输入 #1#

2
100 100 200 200
150 150 250 255

输出 #1#

18000

说明/提示#

对于 20%20\% 的数据,1≤n≤10001 \le n \le 1000。 对于 100%100\% 的数据,1≤n≤1051 \le n \le {10}^5,0≤x1<x2≤1090 \le x_1 < x_2 \le {10}^9,0≤y1<y2≤1090 \le y_1 < y_2 \le {10}^9。

Updated on 4.10 by Dengduck(口胡) & yummy(实现):增加了一组数据。


感觉这里不太好想的倒不是扫描线,而是在区间的处理上… 扫描线的思想很简单,我们在y维度上把正方形的拆分为两个”事件”:进入事件和离开时间,当正方形进入时,我们就把对应正方形的横坐标区间都打上标记,我们利用线段树可以维护出在当前y坐标有多少横坐标区域被正方形占据,这里不容易想的是为什么每次传入的区间是(l,r-1).观察下面的图发现其实在线段树上每个点x掌管的是x向右的这个小方格,所以实际上[l,r]这个区间是被线段树上的[l,r-1]接管了!

Pasted image 20260129210820 当我们每次离开正方形时,就把原来在线段树上打上的标记去掉,利用线段树维护区间并的思想很直观,这里不再赘述.注意我们只需根节点的数据,因此每次都只上传标记即可. 我们每次统计答案的时候实际上是和上面的坐标求差值,这里是因为当我们最后于一次处理y时,能够保证y上的所有离开和进入都能处理完,并且下一个事件的y坐标一定是严格大于当前y,这样求出来的答案一定是对的. 扫描线的进入/离开事件思想实际上用处很广. 代码

#include <algorithm>
#include <bits/stdc++.h>
#include <tuple>
#define ll long long
#define N 100005
#define pr pair<ll, ll>
using namespace std;
int n;
vector<ll> y;
class wei_segment_t {
#define lc x << 1
#define rc x << 1 | 1
public:
struct weisegment_t {
int cover = 0;
ll length = 0;
} tree[N * 8];
void up(int x, int l, int r) {
if (tree[x].cover) {
tree[x].length = y[r + 1] - y[l];
} else {
if (l == r)
tree[x].length = 0;
else
tree[x].length = tree[lc].length + tree[rc].length;
}
}
void modify(int x, int l, int r, int L, int R, int add) {
if (l > R || L > r)
return;
if (l >= L && r <= R) {
tree[x].cover += add;
up(x, l, r);
return;
}
int mid = (l + r) >> 1;
modify(lc, l, mid, L, R, add);
modify(rc, mid + 1, r, L, R, add);
up(x, l, r);
}
} t;
tuple<ll, ll, ll, int> line[N * 2];
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
ll x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2)
swap(x1, x2);
if (y1 > y2)
swap(y1, y2);
line[2 * i - 1] = {x1, y1, y2, 1};
line[2 * i] = {x2, y1, y2, -1};
y.push_back(y1);
y.push_back(y2);
}
y.push_back(-999);
sort(y.begin(), y.end());
sort(line + 1, line + 2 * n + 1);
y.erase(unique(y.begin(), y.end()), y.end());
int len = y.size() - 1;
int pre = 0;
for (int i = 1; i <= 2 * n; i++) {
auto [x, y1, y2, add] = line[i];
ans += t.tree[1].length * (x - pre);
// cout<<t.tree[1].length<<' '<<x<<' '<<pre<<'\n';
pre = x;
int id1 = lower_bound(y.begin(), y.end(), y1) - y.begin();
int id2 = lower_bound(y.begin(), y.end(), y2) - y.begin();
t.modify(1, 1, len - 1, id1, id2 - 1, add);
}
cout << ans;
return 0;
}
P5490 【模板】扫描线 & 矩形面积并
https://sanzenin.top/posts/obsidian/扫描线/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取