扫描线
扫描线：假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。
求面积并
面积 \(=\sum\) 截线段长度 \(\times\) 扫过的高度
现在假设我们有一根线，从下向上扫过图形（从左向右也类似）
- 扫描线可以把整个图形分成许多小矩形，小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
- 线段树是为了维护矩形的长，给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1。每遇到一个矩形时，对标记为 1 的边，加进来这一条矩形的长；扫描到 -1 时，则删除这一条边。
- 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间。
- 需要离散化。
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define ci cs int
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c==45),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(long long x){
if(x<0) x=-x,putchar(45);
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
} using namespace Q;
cs int N=1e5+1;
int n,x[N<<1],m;
long long as;
struct qwq{
int h,l,r,f;
bool operator<(cs qwq &v)cs{
return h<v.h;
}
}o[N<<1];
namespace Tree{
#define ls (rt<<1)
#define rs (rt<<1|1)
int sum[N<<4],len[N<<4];
il void pushup(ci rt,ci l,ci r){
if(sum[rt]) len[rt]=x[r]-x[l];
else len[rt]=len[ls]+len[rs];
}
il void update(ci rt,ci l,ci r,ci q){
if(o[q].l<=x[l]&&x[r]<=o[q].r){
sum[rt]+=o[q].f;
return pushup(rt,l,r);
}
ri int mid=(l+r)>>1;
if(x[mid]>o[q].l) update(ls,l,mid,q);
if(x[mid]<o[q].r) update(rs,mid,r,q);
return pushup(rt,l,r);
}
#undef ls
#undef rs
} using namespace Tree;
signed main(){
n=rd();
for(ri int i=1,x1,y,x2,y_;i<=n;++i){
x1=rd(),y=rd(),x2=rd(),y_=rd();
o[(i<<1)-1]={y,x1,x2,1};
o[i<<1]={y_,x1,x2,-1};
x[(i<<1)-1]=x1,x[i<<1]=x2;
}
n<<=1,sort(o+1,o+1+n);
sort(x+1,x+1+n);
m=unique(x+1,x+n+1)-x-1;
for(ri int i=1;i<n;++i){
update(1,1,m,i);
as+=1ll*len[1]*(o[i+1].h-o[i].h);
}
wt(as);
return 0;
}
求周长并
纵边总长度 \(=\sum 2\times\) 被截得的线段条数 \(\times\) 扫过的高度。
横边总长度 \(=\sum\) | 上次截得的总长 - 现在截得的总长 |
AC·code
// 题解里的代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
const int MAXN = 2e4;
int n, X[MAXN << 1];
int x1, y1, x2, y2, pre = 0; /* 先初始化为 0 */
struct ScanLine {
int l, r, h, mark;
bool operator < (const ScanLine &rhs) const {
if(h == rhs.h) return mark > rhs.mark;
return h < rhs.h;
}
// 注意！这里是后来被 hack 掉以后加上去的
// 如果出现了两条高度相同的扫描线，也就是两矩形相邻
// 那么需要先扫底边再扫顶边，否则就会多算这条边
// 这个对面积并无影响但对周长并有影响
// hack 数据：2 0 0 4 4 0 4 4 8 输出应为：24
} line[MAXN];
struct SegTree {
int l, r, sum, len, c;
// c表示区间线段条数
bool lc, rc;
// lc, rc分别表示左、右端点是否被覆盖
// 统计线段条数(tree[x].c)会用到
} tree[MAXN << 2];
void build_tree(int x, int l, int r) {
tree[x].l = l, tree[x].r = r;
tree[x].lc = tree[x].rc = false;
tree[x].sum = tree[x].len = 0;
tree[x].c = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build_tree(lson, l, mid);
build_tree(rson, mid + 1, r);
}
void pushup(int x) {
int l = tree[x].l, r = tree[x].r;
if(tree[x].sum) {
tree[x].len = X[r + 1] - X[l];
tree[x].lc = tree[x].rc = true;
tree[x].c = 1;
// 做好相应的标记
}
else {
tree[x].len = tree[lson].len + tree[rson].len;
tree[x].lc = tree[lson].lc, tree[x].rc = tree[rson].rc;
tree[x].c = tree[lson].c + tree[rson].c;
// 如果左儿子左端点被覆盖，那么自己的左端点也肯定被覆盖；右儿子同理
if(tree[lson].rc && tree[rson].lc) tree[x].c -= 1;
// 如果做儿子右端点和右儿子左端点都被覆盖，
// 那么中间就是连续的一段，所以要 -= 1
}
}
void edit_tree(int x, int L, int R, int c) {
int l = tree[x].l, r = tree[x].r;
if(X[l] >= R || X[r + 1] <= L) return;
if(L <= X[l] && X[r + 1] <= R) {
tree[x].sum += c;
pushup(x);
return;
}
edit_tree(lson, L, R, c);
edit_tree(rson, L, R, c);
pushup(x);
}
ScanLine make_line(int l, int r, int h, int mark) {
ScanLine res;
res.l = l, res.r = r,
res.h = h, res.mark = mark;
return res;
}
// POJ 不这样做就会CE
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
line[i * 2 - 1] = make_line(x1, x2, y1, 1);
line[i * 2] = make_line(x1, x2, y2, -1);
X[i * 2 - 1] = x1, X[i * 2] = x2;
}
n <<= 1;
sort(line + 1, line + n + 1);
sort(X + 1, X + n + 1);
int tot = unique(X + 1, X + n + 1) - X - 1;
build_tree(1, 1, tot - 1);
int res = 0;
for(int i = 1; i < n; i++) {
edit_tree(1, line[i].l, line[i].r, line[i].mark);
res += abs(pre - tree[1].len);
pre = tree[1].len;
// 统计横边
res += 2 * tree[1].c * (line[i + 1].h - line[i].h);
// 统计纵边
}
res += line[n].r - line[n].l;
// 特判一下枚举不到的最后一条扫描线
printf("%d", res);
return 0;
}