扫描线初探

扫描线初探

tony102

2021 年 10 月 10 日

2081 次浏览

暂无评论

744字数

总结

## 问题引入

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

## 解决

OI-wiki 上的图其实就已经说明了很多事情

![scanline](https://oi-wiki.org/geometry/images/scanning.svg)

图中在 $y$ 轴上从底至上的红色横线就是“扫描线”，我们把所有 $y = k$ 即平行于 $x$ 轴的线（矩形的长），插入进一棵线段树。

每次扫到一条边就算一次面积的话肯定不行。因为上底下都算了一次答案。所以我们可以给下底和上底分别打上 $+1$ 和 $-1$ 的标记。意味着，每当我们碰到 $+1$ 的下底标记时，表示遇到了一个新的矩形，需要计算它的长。等到扫描到 -1 时，证明这一条边需要删除，就删去。

这样子我们只需要枚举每一个矩形的上下两条长边，查线段树上当前所有长的和，乘上与上一条边的差，就可以算出面积。之后把这个矩形的长边插入线段树即可。

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef vector < int > vec;
const int SIZE = 3e5 + 5;

int n; vec nx;

struct node {
    int x, y1, y2, opt;
} a[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

namespace scanLine {
    #define lson(p) (p << 1)
    #define rson(p) (p << 1 | 1)
    int l[SIZE << 3], r[SIZE << 3], sum[SIZE << 3], tag[SIZE << 3];
    void pushUp(int p) {
        if (tag[p] > 0) sum[p] = r[p] - l[p];
        else sum[p] = sum[lson(p)] + sum[rson(p)];
    }
    void build(int p, int L, int R) {
        l[p] = nx[L], r[p] = nx[R];
        if (R - L > 1) {
            int mid = (L + R) >> 1;
            build(lson(p), L, mid), build(rson(p), mid, R);
        }
        pushUp(p);
    }
    void modify(int p, int ql, int qr, int opt) {
        if (l[p] == ql && qr == r[p]) return tag[p] += opt, pushUp(p), void();
        if (r[lson(p)] > ql) modify(lson(p), ql, std::min(qr, r[lson(p)]), opt);
        if (l[rson(p)] < qr) modify(rson(p), std::max(l[rson(p)], ql), qr, opt);
        pushUp(p);
    }
}

signed main() {
    n = read(); int ans = 0; nx.resize(2 * n + 1);
    for (int i = 1, sx, sy, tx, ty; i <= n; ++ i) {
        sx = read(), sy = read(), tx = read(), ty = read();
        a[i] = (node) {sx, sy, ty, 1}, a[i + n] = (node) {tx, sy, ty, -1};
        nx[i] = sy, nx[i + n] = ty;
    }
    std::sort(nx.begin(), nx.end());
    std::sort(a + 1, a + 2 * n + 1, [] (node a, node b) { return a.x < b.x; });
    scanLine::build(1, 1, 2 * n);
    scanLine::modify(1, a[1].y1, a[1].y2, a[1].opt);
    for (int i = 2; i <= 2 * n; ++ i) {
        ans += (a[i].x - a[i - 1].x) * scanLine::sum[1];
        scanLine::modify(1, a[i].y1, a[i].y2, a[i].opt);
    }
    printf("%lld\n", ans);
    return 0;
}
```

## 练习

[Luogu1502 窗口的星星](https://www.luogu.com.cn/problem/P1502)

最后修改：2021 年 10 月 10 日