-
算法自学__扫描线
参考资料：
面积并
给定若干矩形的坐标，求这些矩形构成的图形的面积。
基本思路
上图展示了扫描线的基本思想：以每个矩形的横边为基准，划分整个图形。此时，各个部分都是互不相交的矩形。因此，要求整个图形的面积，只需分别计算每个部分的面积，然后求和即可。
扫描线的实现需要借助线段树。
实现&细节
首先将横边保存在一个结构体数组里，结构体的定义如下：
struct Line{ int l, r, h; int v; //当该横边为某矩形的底边时，v=1；反之，v=0（解释见下文） bool operator<(const Line& l)const{ return h<l.h; //从低到高排序 } Line(int l=0, int r=0, int h=0, int v=0):l(l), r(r), h(h), v(v){} }line[maxn*2];- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
如果正方形的点的横纵坐标很大，会导致线段树的空间消耗过大，所以我们需要对上述结构体中的
l、r进行离散化。线段树的定义如下：
struct TREE{ int l, r; int cnt = 0; //指示该区间是否被完全覆盖，非0代表是，0代表否 //这里的cnt是一个lazy tag，但不需要push_down int len = 0; //该区间被覆盖的长度（不一定完全被覆盖） }tree[maxn<<4];- 1
- 2
- 3
- 4
- 5
- 6
由于线段树中包含
l==r的结点，这是不符合题意的，因为这并不是一条边，而是一个点。所以我们要适当修改线段树的定义，将结点代表区间从[l, r]转化为[l, r+1]。为了得到正确的
len，将push_up定义如下：void push_up(int i){ if(tree[i].cnt){ //完全覆盖 tree[i].len = x[tree[i].r+1]-x[tree[i].l]; }else{ tree[i].len = tree[i<<1].len+tree[i<<1|1].len; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
我们从下向上遍历所有横边，每遍历到一个横边，就根据该横边的信息更新线段树：
void update(int i, int l, int r, int v){ if(tree[i].l>r||tree[i].r<l) return; else if(tree[i].l>=l&&tree[i].r<=r){ tree[i].cnt += v; push_up(i); }else{ int mid = (tree[i].l+tree[i].r)>>1; update(i<<1, l, r, v); update(i<<1|1, l, r, v); push_up(i); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
这就解释了为什么要将
v按照上文的方式定义：由于我们是从下向上扫描，当扫过一个矩形的底边时，该矩形开始“发挥作用”，当扫过一个矩形的顶边时，该矩形的“作用消失”，这一过程可以通过cnt的+1和-1来实现。这里还要着重解释一下
if(tree[i].l>r||tree[i].rtree[i].l>=r或tree[i].r<=l其实也就代表两个区间两个区间没有交集了，但这样会导致错误。回顾上文对于线段树中l和r的定义，我们发现无论是r还是tree[i].r，实际上都要+1，所以两区间没有交集的正确表述应为：tree[i].l>=r+1||tree[i].r+1<=l，这与代码中的表述是等价的。完整代码
#include#include #define int long long #define maxn 100005 using namespace std; struct TREE{ int l, r; int cnt = 0; int len = 0; }tree[maxn<<4]; struct Line{ int l, r, h; int v; bool operator<(const Line& l)const{ return h<l.h; } Line(int l=0, int r=0, int h=0, int v=0):l(l), r(r), h(h), v(v){} }line[maxn*2]; int x1, y1, x2, y2; int x[maxn*2]; int n, m; void push_up(int i){ if(tree[i].cnt){ tree[i].len = x[tree[i].r+1]-x[tree[i].l]; }else{ tree[i].len = tree[i<<1].len+tree[i<<1|1].len; } } void build(int i, int l, int r){ tree[i].l = l, tree[i].r = r; if(l==r) return; int mid = (l+r)>>1; build(i<<1, l, mid); build(i<<1|1, mid+1, r); push_up(i); return; } void update(int i, int l, int r, int v){ if(tree[i].l>r||tree[i].r<l) return; else if(tree[i].l>=l&&tree[i].r<=r){ tree[i].cnt += v; push_up(i); }else{ int mid = (tree[i].l+tree[i].r)>>1; update(i<<1, l, r, v); update(i<<1|1, l, r, v); push_up(i); } } signed main(){ cin>>n; int cnt = 0; for(int i=0;i<n;i++){ scanf("%d %d %d %d", &x1, &y1, &x2, &y2); x[2*i] = x1, x[2*i+1] = x2; line[2*i] = Line(x1, x2, y1, 1); line[2*i+1] = Line(x1, x2, y2, -1); } sort(x, x+2*n); m = unique(x, x+2*n)-x; for(int i=0;i<n;i++){ //离散化 line[2*i].l = lower_bound(x, x+m, line[2*i].l)-x; line[2*i].r = lower_bound(x, x+m, line[2*i].r)-x; line[2*i+1].l = lower_bound(x, x+m, line[2*i+1].l)-x; line[2*i+1].r = lower_bound(x, x+m, line[2*i+1].r)-x; } sort(line, line+2*n); build(1, 0, m-2); int ans = 0; for(int i=0;i<2*n-1;i++){ int l=line[i].l, r=line[i].r, v=line[i].v; update(1, l, r-1, v); ans += tree[1].len*(line[i+1].h-line[i].h); } cout<<ans; return 0; } - 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
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
-
相关阅读:
二次开发真的很难吗？低代码平台有话说
网络连接错误错误代码103怎么解决
pytest(8)-参数化
Python Opencv实践 - 人脸识别CascadeClassifier
互联网摸鱼日报(2023-10-14)
正大国际期货：如何提升外盘恒指交易技巧？
OneFlow源码解析：算子指令在虚拟机中的执行
2023前端面试题
LabVIEW样式检查表1
一步一步开发微信小程序（Django+Mysql）
- 原文地址：https://blog.csdn.net/MaTF_/article/details/126058905
