Klee的算法「线段的并集长度」在C++中

1. 算法介绍

Klee的算法，也称为线段的并集长度问题，是计算一维线段的并集长度的经典问题。给定若干条线段，求它们的并集长度。这个问题可以用扫描线算法来解决，但是时间复杂度是O(N logN)。Klee的算法优化了这个问题，可以在线性时间内解决。

2. 算法思路

Klee的算法是利用了一种简单而重要的性质：线段的并集长度等于所有端点按照从左到右的顺序构成的点集上下标差不为1的点对之间的距离之和。

使用扫描线算法来解决这个问题时，需要先将所有线段进行排序，然后依次扫描每个线段，并且将线段的端点按照从左到右的顺序加入到有序集合中。当扫描到一个线段时，如果它是它所在集合中最左边的线段，或者是它所在集合中最右边的线段，那么它就会对答案产生贡献。

Klee的算法主要思路是对于每个端点，统计它左边和右边与它相邻的点之间的距离，最后累加起来就是答案。

具体来说，可以先对所有端点进行排序，然后依次扫描每个端点。对于每个端点，都可以计算出它左边和右边与它相邻的点之间的距离。然后将这些距离累加起来即可得到答案。

3. 算法实现

下面是Klee的算法的实现代码：

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5 + 5;
int n, cnt;
int x1[MAXN], x2[MAXN], h[MAXN], pos[MAXN << 1];
double len[MAXN << 1];
vector<int> v[MAXN << 1];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d%d", &x1[i], &x2[i], &h[i]);
        pos[++cnt] = x1[i];
        pos[++cnt] = x2[i];
    }
    sort(pos + 1, pos + cnt + 1);
    cnt = unique(pos + 1, pos + cnt + 1) - pos - 1;
    for(int i = 1; i <= n; i++) {
        x1[i] = lower_bound(pos + 1, pos + cnt + 1, x1[i]) - pos;
        x2[i] = lower_bound(pos + 1, pos + cnt + 1, x2[i]) - pos;
        v[x1[i]].push_back(i);
        v[x2[i]].push_back(-i);
    }
    double res = 0;
    for(int i = 1; i < cnt; i++) {
        double d = (double)(pos[i + 1] - pos[i]);
        for(int j = 0; j < v[i].size(); j++) {
            int id = abs(v[i][j]);
            int k = (v[i][j] > 0) ? x2[id] : x1[id];
            len[id] += d * (h[k] - h[i]) / (pos[k] - pos[i]);
            if(len[id] >= 0) res += d;
        }
    }
    printf("%.2lf\n", res);
    return 0;
}

（1） 输入处理

首先，读入n个线段，每个线段由两个端点$x1$和$x2$，以及一个高度$h$组成。我们可以将每个线段看作一个三元组$(x1, x2, h)$，然后将所有三元组按照$x1$从小到大的顺序排序。

scanf("%d", &n);

for(int i = 1; i <= n; i++) {
    scanf("%d%d%d", &x1[i], &x2[i], &h[i]);
}
for(int i = 1; i <= n; i++) {
    if(x1[i] > x2[i]) swap(x1[i], x2[i]);
}
for(int i = 1; i <= n; i++) {
    for(int j = i + 1; j <= n; j++) {
        if(x1[i] <= x1[j] && x1[j] <= x2[i] && x2[i] <= x2[j]) {
            swap(x1[i], x1[j]);
            swap(x2[i], x2[j]);
            swap(h[i], h[j]);
        }
    }
}

为了方便，我们排序后将所有的端点和y轴上的点统一成一个点集，然后将x轴上的坐标离散化成编号从1到cnt的整数，这样每个点的x坐标就可以用一个整数来表示。这个过程可以用STL中的sort和unique函数来实现，示例如下：

for(int i = 1; i <= n; i++) {

    pos[++cnt] = x1[i];
    pos[++cnt] = x2[i];
}
sort(pos + 1, pos + cnt + 1);
cnt = unique(pos + 1, pos + cnt + 1) - pos - 1;

x1和x2中原来的坐标可以用离散化之后的编号来表示：

for(int i = 1; i <= n; i++) {

    x1[i] = lower_bound(pos + 1, pos + cnt + 1, x1[i]) - pos;
    x2[i] = lower_bound(pos + 1, pos + cnt + 1, x2[i]) - pos;
}

为了记录每个点对应的线段，我们可以使用一个vector数组来存储，将线段的编号加入到对应的位置中即可：

for(int i = 1; i <= n; i++) {

    v[x1[i]].push_back(i);
    v[x2[i]].push_back(-i);
}

（2） 算法实现

最终的算法实现需要依次扫描x轴上的每个点，然后对于每个点，计算出它左边和右边与它相邻的点之间的距离，然后将这些距离累加起来即可得到答案。

具体来说，我们循环遍历1到cnt - 1，对于每个i，计算出pos[i]和pos[i + 1]之间的距离d，然后遍历v[i]中的所有线段，并累加它们在这个区间内的长度贡献。需要注意的是，如果一个线段的长度贡献小于0，那么它就不对答案产生贡献。

double res = 0;

for(int i = 1; i < cnt; i++) {
    double d = (double)(pos[i + 1] - pos[i]);
    for(int j = 0; j < v[i].size(); j++) {
        int id = abs(v[i][j]);
        int k = (v[i][j] > 0) ? x2[id] : x1[id];
        len[id] += d * (h[k] - h[i]) / (pos[k] - pos[i]);
        if(len[id] >= 0) res += d;
    }
}
printf("%.2lf\n", res);

4. 总结

Klee的算法是求解线段的并集长度的经典算法，可以在线性时间内解决这个问题。它的主要思路是利用点集上下标差不为1的点对之间的距离之和等于线段的并集长度这个重要性质，对每个端点计算出左边和右边与它相邻的点之间的距离，然后累加起来即可。这个算法虽然比扫描线算法要简单，但是依然需要比较高的编程能力。