「JOI 2014 Final」裁剪线 题解

问题分析

我们有一张 $W \times H$ 的矩形纸，上面有 $N$ 条平行于坐标轴的裁剪线。这些裁剪线将纸分割成若干区域，我们需要计算区域的数量。

这是一个典型的平面图区域计数问题，可以使用欧拉公式来解决。

核心算法

1. 欧拉公式

对于平面图，欧拉公式为：

$$V - E + F = 1 + C$$

其中：

• $V$ = 顶点数
• $E$ = 边数
• $F$ = 面数（包括外部无限面）
• $C$ = 连通分量数

在我们的问题中，最终的区域数 $F_{\text{inner}} = F - 1$（去掉外部无限面）。

2. 算法框架

代码的主要思路：

1. 离散化：由于 $W, H$ 可达 $10^9$，但 $N \leq 10^5$，需要离散化坐标
2. 线段合并：合并相邻的平行线段，减少冗余边
3. 计算交点：使用扫描线算法计算水平线和垂直线的交点
4. 应用欧拉公式：统计顶点、边、连通分量，计算区域数

代码详解

离散化处理

vector<int> vx, vy;  // 离散化坐标

// 添加边界和所有线段的端点
add(0, 0, 0, B);     // 左边界
add(A, 0, A, B);     // 右边界  
add(0, 0, A, 0);     // 下边界
add(0, B, A, B);     // 上边界

// 离散化坐标
deal(vx);  // 排序并去重
deal(vy);

线段合并

// 合并垂直线段（x坐标相同）
REP(i, 0, vx.size()) {
    sort(all(t1[i]));  // 按y坐标排序
    int mx = -1, L = -1;
    
    for (auto [l, r] : t1[i]) {
        if (mx < l) {  // 不重叠
            if (mx != -1) 
                a[tot++] = {i, L, i, mx};  // 保存前一段
            L = l;
            mx = r;
        } else {  // 重叠，合并
            mx = max(mx, r);
        }
    }
    if (mx != -1) 
        a[tot++] = {i, L, i, mx};  // 保存最后一段
}

水平线段也进行类似的合并处理。

扫描线计算交点

使用树状数组（BIT）来维护当前扫描线穿过的垂直线段：

struct BIT {
    int n;
    int b[400005];
    void upd(int x, int y) {  // 在位置x增加y
        ++x;
        while (x <= n) 
            b[x] += y, x += x & -x;
    }
    int ask(int l, int r) {  // 查询区间和
        int res = 0; ++r;
        while (r) res += b[r], r -= r & -r;
        while (l) res -= b[l], l -= l & -l;
        return res;
    }
} bit;

连通分量计算

使用并查集维护线段的连通性：

struct rectan {
    void work2(int id = 0) {
        if (x == X)  // 垂直线段
            ad[x].pb({y, Y, id});
        else  // 水平线段  
            b.pb({y, x, X}), ad2[x].pb({y, 1, id}), ad2[X + 1].pb({y, -1, id});
    }
};

REP(i, 0, n) fa[i] = i;  // 初始化并查集

// 扫描过程中合并相交的线段
if (it2->first <= min(r, it->second)) {
    fa[findfa(id)] = findfa(it2->second);  // 合并连通分量
}

最终答案计算

int ans = -n;  // 初始化为 -E（边数）

// 应用欧拉公式：F = E - V + C + 1
// 这里 ans 最终等于 F - 1 = (E - V + C + 1) - 1 = E - V + C
REP(i, 0, n) if (fa[i] == i) 
    ++ans;  // 加上连通分量数 C

over(ans)  // 输出最终区域数

算法正确性

1. 欧拉公式应用

对于平面图：

• 原公式：$V - E + F = 1 + C$
• 我们需要内部面数：$F_{\text{inner}} = F - 1 = E - V + C$

代码中：

• ans 初始化为 $-n$（$-E$，边数）
• 扫描过程中 ans += bit.ask(l, r) 统计交点（增加 $V$）
• 最后 ++ans 对每个连通分量（增加 $C$）
• 最终 ans = -E + V + C = F - 1

2. 边界处理

通过添加四条边界线，确保整个平面图是连通的，且外部无限面明确。

3. 离散化正确性

由于裁剪线端点都是整数坐标，且线段平行于坐标轴，离散化不会改变拓扑结构。

复杂度分析

• 离散化：$O(N \log N)$
• 线段合并：$O(N \log N)$
• 扫描线：$O(N \log N)$
• 并查集：$O(N \alpha(N))$
• 总复杂度：$O(N \log N)$

对于 $N \leq 10^5$ 可以接受。

示例验证

样例 1

输入：

10 10 5
6 0 6 7
0 6 7 6  
2 3 9 3
2 3 2 10
1 9 8 9

处理过程：

1. 离散化坐标，合并线段
2. 计算交点：各线段相交形成网格
3. 统计：$V = 9, E = 12, C = 1$
4. $F = E - V + C + 1 = 12 - 9 + 1 + 1 = 5$
5. 内部区域：$F - 1 = 4$

输出：4

样例 2

更复杂的网格结构，通过相同方法计算得到 5 个区域。

总结

本题通过以下技巧解决了大规模平面图区域计数问题：

1. 离散化处理大坐标范围
2. 线段合并减少冗余计算
3. 扫描线算法高效计算交点
4. 欧拉公式将区域计数转化为图论问题
5. 并查集维护连通性

这种组合方法能够在 $O(N \log N)$ 时间内解决 $N \leq 10^5$ 的大规模数据。