题目背景

墙上贴着许多形状相同的海报、照片。它们的边都是水平和垂直的。每个矩形图片可能部分或全部的覆盖了其他图片。所有矩形合并后的边长称为周长。

题目描述

编写一个程序计算周长。

如图 $1$ 所示 $7$ 个矩形。

如图 $2$ 所示，所有矩形的边界。所有矩形顶点的坐标都是整数。

输入格式

输入文件的第一行是一个整数 $N$，表示有多少个矩形。接下来 $N$ 行给出了每一个矩形左下角坐标和右上角坐标。

输出格式

输出文件只有一个正整数，表示所有矩形的周长。

输入输出样例 #1

输入 #1

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

输出 #1

228

说明/提示

数据范围及约定

对于全部数据，$1\le N<5000$，所有坐标的数值范围都在 $-10^4$ 到 $10^4$ 之间。

测试链接： https://www.luogu.com.cn/problem/P1856

C++

#include <bits/stdc++.h>
using namespace std;

// 扫描线结构体
typedef struct ScanLine {
    int loc, start, end, type;
    // loc: 扫描线位置
    // start, end: 区间范围
    // type: 1 表示入边，-1 表示出边

    ScanLine(int loc, int s, int e, int v) : loc(loc), start(s), end(e), type(v) {}

    // 排序规则：先按位置从小到大，位置相同时入边优先
    bool operator<(ScanLine &other) const {
        if (loc != other.loc) {
            return loc < other.loc;
        } else {
            return type > other.type;
        }
    }
} ScanLine;

// 线段树节点结构体
typedef struct Node {
    int l, r;        // 区间范围
    int length;      // 当前区间被覆盖的总长度
    int times;       // 被覆盖的次数
    Node *left, *right;

    Node(int l, int r) : l(l), r(r), length(0), times(0), left(nullptr), right(nullptr) {}
} Node;

// 线段树类
class SegmetTree {
private:
    Node *root;

    // 向上更新当前节点的覆盖长度
    void pushup(Node *tree) {
        int l = tree->l, r = tree->r;
        if (tree->times > 0) {
            // 当前区间被完全覆盖
            tree->length = r - l + 1;
        } else {
            // 否则从左右子节点中累加覆盖长度
            int length = tree->left ? tree->left->length : 0;
            if (tree->right) {
                length += tree->right->length;
            }
            tree->length = length;
        }
    }

    // 更新区间 [jobl, jobr] 的覆盖次数，v = +1 表示加入一条边，-1 表示删除一条边
    void update(Node *tree, int jobl, int jobr, int v) {
        int l = tree->l, r = tree->r;
        if (jobl <= l && r <= jobr) {
            tree->times += v;
        } else {
            int mid = (l + r) >> 1;
            if (jobl <= mid) {
                if (tree->left == nullptr) tree->left = new Node(l, mid);
                update(tree->left, jobl, jobr, v);
            }
            if (mid < jobr) {
                if (tree->right == nullptr) tree->right = new Node(mid + 1, r);
                update(tree->right, jobl, jobr, v);
            }
        }
        pushup(tree);
    }

    // 重置整棵树（用于第二次扫描）
    void reset(Node *tree) {
        if (tree == nullptr) return;
        tree->length = tree->times = 0;
        reset(tree->left);
        reset(tree->right);
    }

public:
    SegmetTree(int l, int r) {
        this->root = new Node(l, r);
    }

    void update(int l, int r, int v) {
        update(root, l, r, v);
    }

    int coverLength() {
        return root->length;
    }

    void reset() {
        reset(root);
    }
};

// 坐标值范围，可根据题目数据调整
const int L = -10010, R = 10010;

int main() {
    int n;
    cin >> n;

    // 用于存储两次扫描线的集合
    vector<ScanLine> xline, yline;

    // 读取所有矩形，拆分为扫描线
    for (int i = 0, x1, y1, x2, y2; i < n; i++) {
        cin >> x1 >> y1 >> x2 >> y2;

        // 横向扫描（扫描x，更新y区间）
        xline.emplace_back(x1, y1, y2, 1);   // 左边
        xline.emplace_back(x2, y1, y2, -1);  // 右边

        // 纵向扫描（扫描y，更新x区间）
        yline.emplace_back(y1, x1, x2, 1);   // 下边
        yline.emplace_back(y2, x1, x2, -1);  // 上边
    }

    // ------------------- 横向扫描 -------------------
    int rst = 0, prevLength = 0;
    sort(xline.begin(), xline.end());

    SegmetTree segmetTree(L, R);
    for (int i = 0; i < 2 * n; i++) {
        segmetTree.update(xline[i].start, xline[i].end - 1, xline[i].type);
        int length = segmetTree.coverLength();
        int d = abs(length - prevLength);
        rst += d;
        prevLength = length;
    }

    // ------------------- 纵向扫描 -------------------
    sort(yline.begin(), yline.end());
    segmetTree.reset();
    prevLength = 0;

    for (int i = 0; i < 2 * n; i++) {
        segmetTree.update(yline[i].start, yline[i].end - 1, yline[i].type);
        int length = segmetTree.coverLength();
        int d = abs(length - prevLength);
        rst += d;
        prevLength = length;
    }

    // 输出总周长
    cout << rst << endl;
    return 0;
}

🎯 为什么扫描线排序位置相同先入边再出边？

这是个非常关键也很容易忽略的细节！
我们在使用扫描线算法时，将“位置相同”的扫描线按照「入边优先、出边靠后」的顺序处理，是为了防止遗漏或者错误更新重叠区域的覆盖次数。

问题核心：为什么相同位置要先处理入边？

假设你有两个矩形，它们在某一个位置，比如 x=1，都有边：

• 矩形A的左边界（入边）：x = 1，y ∈ [0, 1]
• 矩形B的右边界（出边）：x = 1，y ∈ [0, 1]

如果我们在这个位置处理扫描线：

• 若先处理出边，会将 [0, 1] 的覆盖次数减少，但由于矩形A的入边尚未处理，这段区间的覆盖就会短暂为 0，导致计算周长变化时出现误判。
• 若先处理入边，覆盖次数 +1，这时后处理出边时 -1，最终 [0, 1] 仍然保持正确的“被1个矩形覆盖”的状态，不会出现中断。

2
0 0 1 1
1 0 2 1

✅ 换句话说：

• 入边先处理：可以及时更新被新矩形覆盖的区间，保证 times > 0，不会错误地被认为是“没有覆盖”；
• 出边后处理：是在已经被处理过的基础上，把当前矩形的影响移除。

---

🧠 类比一下：

就像上课的时候，一个人刚走进教室（入边），另一个人刚离开（出边）。你要先数“现在在教室的人”，当然应该先把新进来的人算上，再去除出去的人。否则你会一度以为没人。

---

📌 在代码中对应的逻辑：

bool operator<(ScanLine &other) const {
    if (loc != other.loc) {
        return loc < other.loc;
    } else {
        return type > other.type; // 入边(type=1) 在前，出边(type=-1) 在后
    }
}

这里 type > other.type 保证：

• 1（入边） 会排在 -1（出边） 前面

---