
P5490 【模板】扫描线 & 矩形面积并
题目描述
求 个四边平行于坐标轴的矩形的面积并。
输入格式
第一行一个正整数 。
接下来 行每行四个非负整数 ,表示一个矩形的四个端点坐标为 。
输出格式
一行一个正整数,表示 个矩形的并集覆盖的总面积。
输入输出样例 #1
输入 #1
2100 100 200 200150 150 250 255输出 #1
18000说明/提示
对于 的数据,。 对于 的数据,,,。
Updated on 4.10 by Dengduck(口胡) & yummy(实现):增加了一组数据。
感觉这里不太好想的倒不是扫描线,而是在区间的处理上… 扫描线的思想很简单,我们在y维度上把正方形的拆分为两个”事件”:进入事件和离开时间,当正方形进入时,我们就把对应正方形的横坐标区间都打上标记,我们利用线段树可以维护出在当前y坐标有多少横坐标区域被正方形占据,这里不容易想的是为什么每次传入的区间是(l,r-1).观察下面的图发现其实在线段树上每个点x掌管的是x向右的这个小方格,所以实际上[l,r]这个区间是被线段树上的[l,r-1]接管了!
当我们每次离开正方形时,就把原来在线段树上打上的标记去掉,利用线段树维护区间并的思想很直观,这里不再赘述.注意我们只需根节点的数据,因此每次都只上传标记即可.
我们每次统计答案的时候实际上是和上面的坐标求差值,这里是因为当我们最后于一次处理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;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
最后更新于 ,距今已过 74 天
部分内容可能已过时