Advent of Code 2025 - 第8天题解

核心任务描述

给定 $N$ 个三维空间内的点，每个点坐标 $(x, y, z)$ 均为非负整数。同时确保每个点坐标唯一，且任意两个点之间的欧氏距离互不相等。试计算：

所有点对之间的前 $K$ 短距离，并输出将其作为边连接后，前三大连通分量的大小之积；
按照边的添加顺序，输出在所有点被连接之前，最后一次添加边时，该边所连接的两个点的 $x$ 坐标之积。

思考过程

拆解问题

这个题目的需求比较复杂，我们首先需要将其拆解为几个子问题。对于第一问，我们需要：

找出所有点对之间的欧氏距离中前 $K$ 短距离；
使用这些距离作为边，构建图并找到连通分量；
计算前三大连通分量的大小之积。

对于第二问，我们需要：

按照边的添加顺序，逐步连接点；
在所有点被连接之前，记录最后一次添加边时所连接的两个点的 $x$ 坐标之积。

不难发现，第一问中我们可以用并查集来管理连通分量，而第二问中我们也同样需要使用并查集来检查点的连接状态。这并不是什么难事，因此最大的挑战均在于每个问题的第一步：如何高效地找到所有点对之间的前 $K$ 短距离或者将点按距离顺序连接起来。

并行优化

对于找寻前 $K$ 短距离以及前 $3$ 大连通分量，我们可以用最大/最小堆来辅助计算。当然，最耗时的步骤是计算所有点对之间的距离。为此，我们可以使用一些简单的并行优化手段：

替代欧氏距离：由于我们只需要比较距离的大小关系，而不需要具体的距离值，我们可以使用欧氏距离的平方来代替欧氏距离本身进行比较。这样我们只需要使用整数的乘法和加法，避免了浮点数的开方运算，从而提升计算速度。
避免重复计算：由于欧氏距离是对称的，我们只需要计算每对点一次，避免重复计算。我们可以只计算 $i < j$ 的点对 $(p_i, p_j)$ 。
并行处理：利用并行计算库，可以将所有需要计算的任务拆分为 $M$ 份，每一份由一个线程处理，最后将结果合并。这可以显著减少计算时间，尤其是在多核处理器上。

并行归约

在并行计算中，归约 (reduce)是一种常见的计算模式：对于 $M$ 个类型为 $A$ 的输入数据，通过一个二元操作符 $f: A\times A\to A$ ，将其归约为一个类型为 $A$ 的输出结果。并行化的归约操作中 $f$ 需要满足结合律，即对于任意的 $a, b, c$ ，都有 $f(f(a, b), c) \equiv f(a, f(b, c))$ 。比如在本题中，我们合并两个堆时，输出的仍是一个堆，并且满足结合律。对于这样的操作，我们可以将输入数据划分为若干份，分别在多个线程中进行归约操作，常见的模式是如下图所示的树形结构：

如果是折叠 (fold)操作，其操作的函数类型为 $g: A\times B\to A$ ，则在并行化时通常只需要将第一层操作替换为 $g: A\times B\to A$ ，其余层仍然使用 $f: A\times A\to A$ 进行归约。这也是在 rayon 中实现并行折叠的模式。

这样的话我们就已经能够解决第一问了：

1
let mut dsu = DisjointSet::new(self.nodes.nrows());
2
(0..self.nodes.nrows())
3
    .into_par_iter()
4
    .flat_map_iter(|i| {
5

6
        ((i + 1)..self.nodes.nrows())
7
            .map(|j| (i, j))
8
            .collect::<Vec<_>>()
9
    })
10

11
    .fold(BinaryHeap::new, |mut heap, (i, j)| {
12
        let d = self.dist(i, j);
13
        heap.push((d, i, j));
14
        if heap.len() > self.max_steps {
15
            heap.pop();
16
        }
17
        heap
18
    })
19

20
    .reduce(BinaryHeap::new, |mut acc, mut heap| {
21
        acc.extend(heap.drain());
22
        while acc.len() > self.max_steps {
23
            acc.pop();
24
        }
25
        acc
26
    })
27
    .into_iter()
28
    .for_each(|(_, i, j)| dsu.union(i, j));
29
dsu.sizes
30
    .values()
31

32
    .fold(BinaryHeap::new(), |mut heap, &size| {
33
        heap.push(Reverse(size));
34
        if heap.len() > 3 {
35
            heap.pop();
36
        }
37
        heap
38
    })
39
    .iter()
40
    .map(|&Reverse(x)| x)
41
    .product::<u64>()
42
    .to_string()

在第二问中，直接计算出所有边并排序显然是不现实的，因为我们需要处理的边数将是 $O(N^2)$ 级别的。为此，我们需要一些优化来减少计算。不难发现，由于我们只关心最后一条将所有点连成一个连通分量的边，因此我们实际上并不需要关心那些不会连接不同连通分量的边。基于这一点，我们可以使用如下策略：

基于点的最短边集：对于每个点，我们只计算其与属于不同连通分量的点之间的最短边，并将这些边加入候选边集中。这样可以大幅减少需要计算的边数。
动态更新边集：在每次从边集中取走最短边 $(u,v)$ 后，我们需要重新计算从 $u$ 出发，连接到其他连通分量的最短边，并将这条边加入边集中。这样可以确保尽在需要时更新边集，避免不必要的计算。
循环直到所有点连通：重复上述过程，直到所有点都属于同一个连通分量为止。在这个过程中，我们记录最后一条连接不同连通分量的边 $(u,v)$ ，并输出其 $x$ 坐标之积。

根据这个思路，我们可以实现如下代码：

1
let mut closest_neighbor = (0..self.nodes.nrows())
2
    .into_par_iter()
3
    .map(|i| {
4
        (0..self.nodes.nrows())
5
            .filter_map(|j| (j != i).then_some((self.dist(i, j), i, j)))
6
            .min_by_key(|&(dist, _, _)| dist)
7
            .map_or_else(
8
                || unreachable!("There should be at least one other node"),
9
                Reverse,
10
            )
11
    })
12
    .collect::<BinaryHeap<_>>();
13
let mut dsu = DisjointSet::new(self.nodes.nrows());
14
loop {
15
    let Some(Reverse((_, i, j))) = closest_neighbor.pop() else {
16
        panic!("No more edges to process");
17
    };
18

19
    let root_i = dsu.find(i);
20
    let root_j = dsu.find(j);
21
    if root_i != root_j {
22
        dsu.union(i, j);
23
    }
24

25
    if dsu.sizes.len() == 1 {
26
        return (self.nodes[[i, 0]] * self.nodes[[j, 0]]).to_string();
27
    }
28

29
    closest_neighbor.push(
30
        (0..self.nodes.nrows())
31
            .filter_map(|k| (root_i != dsu.find(k)).then_some((self.dist(i, k), i, k)))
32
            .min_by_key(|&(dist, _, _)| dist)
33
            .map_or_else(
34
                || unreachable!("At least one different component should exist"),
35
                Reverse,
36
            ),
37
    );
38
}

八叉树表示

在上述方法中，尽管我们利用并行计算和一些动态更新策略减少了计算时间，但计算量仍然是 $O(N^2)$ 级别的，面对非常大的数据集时，仍然可能无法在合理时间内完成计算。即便是如本题中仅有 $N=1,000$ ，使用上述算法也需要 $21 ms$ 和 $281 ms$ 的时间。为此，我们需要进一步优化算法。

对于空间中的点对距离问题，我们很自然可以想到使用八叉树来划分空间。在八叉树中，空间将会被递归地划分为八个象限（如下图所示），从而使得我们可以快速地定位到某个点所在的空间区域，并且理论上可以高效地查询某个点在空间中的邻近点。

**八叉树划分空间**
不同颜色的立方体表示不同层级的八叉树节点，每个节点包含其子节点所覆盖的空间

值得注意的是，在本题中，由于每个点的坐标均为整数，我们实际上可以使用 Morton 编码，也即Z-序曲线 (Z-ordercurve)来对空间进行划分。Morton 编码通过将每个坐标的二进制位交错排列，生成一个一维的编码值，从而实现空间的线性化表示，如下图所示：

**Morton 编码**
将 $(x, y, z)$ 坐标的二进制位交错排列，生成 Morton 编码值

魔法位运算

正如 Jeroen Baert 在他的博客中所描述的那样，我们可以使用一些“魔法位运算”来高效地交织 (interleave)二进制位。具体来说，我们可以通过一系列的位移和掩码操作，将每个坐标的二进制位分散开来（反之亦然），从而实现交错排列。如下所示：

1
const fn interleave_bits_by_3(x: i64) -> u64 {
2
    let mut x = x.cast_unsigned() & 0x1ff_fff;
3
    x = (x | (x << 32)) & 0x1f_000_000_00f_fff;
4
    x = (x | (x << 16)) & 0x1f_000_0ff_000_0ff;
5
    x = (x | (x << 8)) & 0x1_00f_00f_00f_00f_00f;
6
    x = (x | (x << 4)) & 0x1_0c3_0c3_0c3_0c3_0c3;
7
    x = (x | (x << 2)) & 0x1_249_249_249_249_249;
8
    x
9
}

**魔法位运算**
通过位移和掩码操作，可以在数个步骤内实现二进制位的交织，而不需要循环

利用 Morton 编码，我们可以将空间中的点按照其 Morton 编码值进行排序，此时我们可以得到一条类似于下面这样的分形曲线：

**Z-序曲线**
按照 Morton 编码值排序后的点在空间中的分布构成一个遍历八个象限的分形曲线

Morton 编码值实际上隐含了对一个多维空间中的层级划分。由于我们将三维坐标的二进制位交错排列，因此在编码中每三位可以看作是一个层级，每个层级中的三位二进制数表示该层级中所在的八个象限之一。因此，我们实际上通过按照 Morton 编码排序已经隐式构建了一个八叉树结构，任意一个八叉树节点都可以表示为一个 Morton 编码值的前缀和/或一个对应的数组区间。

分支定界

在有了八叉树结构后，我们可以利用空间划分来加速最近邻搜索，也就是分支定界 (branchand bound)。在搜索的过程中，我们在已经得到了若干个最近邻候选点后，可以利用当前的最短距离来剪枝八叉树中的节点。具体来说，假设当前最近邻距离为 $d$ ，我们在搜索过程中遇到一个八叉树节点时，可以计算该节点所覆盖的空间与查询点之间的最小距离 $d_{\min}$ 。如果 $d_{\min} \geq d$ ，则说明该节点及其子节点中的所有点都不可能是更近的邻居，因此可以直接跳过该节点，避免不必要的计算。

由于在这两问中，我们都需要考虑所有点之间的距离，因此我们可以改用双树遍历 (dual-treetraversal)的方法来批次处理点对之间的计算。比如以第一问为例，我们可以将所有点构建为八叉树的根节点，然后遍历：

对于当前的节点对 $(L, R)$ ，计算其覆盖空间之间的最小距离 $d_{\min}$ ；
（定界） 如果 $d_{\min}$ 大于当前已知的第 $K$ 大距离，则跳过该节点对；
（批次计算） 否则，如果 $L$ 和 $R$ 的大小低于某个阈值，则直接计算 $L$ 和 $R$ 中所有点对之间的距离，并更新最近邻堆；
（分支） 否则，按照以下规则产出新的节点对并继续遍历：
- 如果 $L$ 和 $R$ 是同一个节点，则产出所有不重复的子节点两两组合的节点对（ $i \le j$ ）；
- 否则，分裂较大的节点，产出其子节点与另一个节点的所有组合的节点对。

在计算 $d_{\min}$ 时，我们可以利用 Morton 编码的性质来快速估计两个节点覆盖空间之间的最小距离。具体来说，每个节点对应一个 Morton 编码值的前缀，其所有子节点对应的 Morton 编码值均以该前缀开头。因此我们可以从该前缀中提取出对应的坐标范围，从而得到该节点对应的按坐标轴排列的包围盒 (Axis-AlignedBounding Box)（AABB）。然后，我们可以使用 AABB 之间的距离计算方法在 $O(1)$ 时间内得到 $d_{\min}$ 。

前缀估计的 AABB 与实际 AABB

由前缀估计得到的 AABB 为理论上最大的包围盒，实际节点所包含的点集可能分布得更紧凑，从而导致实际 AABB 更小，如下图所示：

当点集分布较为均匀时，这种差异通常较小；但当点集分布极为不均匀时，差异可能会很大，从而影响剪枝效果。因此，在实际实现中，我们可以在构建八叉树时，预先计算出每个节点的实际 AABB，从而提升剪枝路径的命中率。

这样一来，我们就可以高效地计算所有点对之间的前 $K$ 短距离，进而解决第一问。但是第二问呢？由于第二问中我们需要动态地更新连通分量，因此无法像第一问那样知道需要计算多少条边，从而无法直接使用双树遍历的方法。为此，我们还需要进一步改进。

最小生成树

实际上，我们可以重新审视第二问的需求。在之前的分析中，我们已经得出结论：我们只需要关注那些连接不同连通分量的边。这个过程实际上就是 Kruskal 算法构建最小生成树 (MinimumSpanning Tree)（MST）的过程。而最后一条边则是这个最小生成树中的最长边。由于最小生成树的唯一性，如果我们可以直接构建最小生成树，那么我们就可以更快地找到这条边。

证明最小生成树的唯一性

对于一个加权无向图 $\mathcal{G}$ ，如果所有边的权重均不相等，那么 $\mathcal{G}$ 的最小生成树是唯一的。

反证法证明：假设 $\mathcal{G}$ 上存在两棵不同的最小生成树 $T_1$ 和 $T_2$ ， $T_1 \ne T_2$ 。由于它们不同，必然存在一条边 $e_1$ 属于 $T_1$ 但不属于 $T_2$ （ $\exists e_1 \in T_1, e_1 \notin T_2$ ）。如果将 $e_1$ 从 $T_1$ 中移除，则 $T_1 \setminus \{e_1\}$ 会变成两个连通分量 $C_1$ 和 $C_2$ 。

由于 $T_2$ 是连通的，必然存在一条边 $e_2$ 属于 $T_2$ 但不属于 $T_1$ （ $\exists e_2 \in T_2, e_2 \notin T_1$ ），且连接 $C_1$ 和 $C_2$ 。这是因为，如果这样的边不存在，即 $C_1$ 和 $C_2$ 在 $T_2$ 中也完全使用来自 $T_1 \setminus \{e_1\}$ 的边连接，那么原先 $T_1$ 中就已经存在一个环路，与 $T_1$ 为生成树矛盾。

此时，我们可以比较 $e_1$ 和 $e_2$ 的权重。由于所有边的权重均不相等，必然有 $w(e_1) \neq w(e_2)$ 。假设 $w(e_1) < w(e_2)$ ，则我们可以构造一棵新的生成树 $T_3 = T_2 \setminus \{e_2\} \cup \{e_1\}$ ，其总权重小于 $T_2$ 的总权重，这与 $T_2$ 为最小生成树矛盾。同理，如果 $w(e_1) > w(e_2)$ ，则我们可以构造一棵新的生成树 $T_4 = T_1 \setminus \{e_1\} \cup \{e_2\}$ ，其总权重小于 $T_1$ 的总权重，这与 $T_1$ 为最小生成树矛盾。

因此，假设不成立， $\mathcal{G}$ 的最小生成树是唯一的。

事实上，我们确实有更快的构建最小生成树的算法，比如 Borůvka 算法。该算法的核心思想是：

初始化时，每个点作为一个独立的连通分量；
对于每个连通分量，找到其与其他任意连通分量之间的最短边；
将这些边加入最小生成树中，同时合并这些连通分量；
重复步骤 2 和 3，直到所有点都属于同一个连通分量为止。

利用和八叉树结合的双树遍历方法，我们可以高效地找到每个连通分量的最短边，从而快速构建最小生成树。并且我们可以添加一个额外的剪枝条件：如果当前处理的两个节点所属的连通分量已经相同，则跳过该节点对。完整的算法流程如下：

初始化所有点为独立的连通分量；
初始化每个连通分量的对短距离为无穷大；
将根节点对 $(root, root)$ 入栈；
重复以下步骤直到栈为空：
1. 对于栈顶的节点对 $(L, R)$ ，计算其覆盖空间之间的最小距离 $d_{\min}$ ；
2. 如果 $d_{\min}$ 大于 $L$ 和 $R$ 中包含的连通分量的最短距离的最大值，则跳过该节点对；
3. 如果 $L$ 和 $R$ 所属的连通分量相同，则跳过该节点对；
4. 如果 $L \times R$ 的大小低于某个阈值，则直接计算 $L$ 和 $R$ 中所有点对之间的距离，并更新每个连通分量的最短距离；
5. 否则，按照以下规则产出新的节点对入栈：
  - 如果 $L$ 和 $R$ 是同一个节点，则产出所有不重复的子节点两两组合的节点对（ $i \le j$ ）；
  - 否则，分裂较大的节点，产出其子节点与另一个节点的所有组合的节点对。
使用每个连通分量的最短边合并连通分量，并记录更新记录最长的边。
重复步骤 2 到 5，直到所有点都属于同一个连通分量为止。

核心算法实现

在本题的实际实现中，由于点集规模较小，我们实际可以采用一些细节上的优化：

完整构建八叉树，确定每个节点对应的点集区间，避免在遍历过程中频繁地进行点集划分；
预计算每个节点的实际边界盒，从而得到比依赖 Morton 编码前缀估计的更紧凑的边界盒，提升剪枝路径命中率
第二问中，每次循环时，预先计算出所有节点包含的连通分量，避免在遍历过程中频繁地进行并查集查询。

1
impl Puzzle {
2

3
    fn deeper_search_nodes(
4
        &self,
5
        left_node_idx: usize,
6
        right_node_idx: usize,
7
    ) -> Vec<(usize, usize)> {
8

9
        if left_node_idx == right_node_idx {
10
            let children = &self.octree_children[left_node_idx];
11
            return children
12
                .iter()
13
                .enumerate()
14
                .flat_map(|(idx, &i)| children[idx..].iter().map(move |&j| (i, j)))
15
                .collect();
16
        }
17

18
        if self.octree[left_node_idx].size() > self.octree[right_node_idx].size() {
19
            self.octree_children[left_node_idx]
20
                .iter()
21
                .map(|&child| (child, right_node_idx))
22
                .collect()
23
        } else {
24
            self.octree_children[right_node_idx]
25
                .iter()
26
                .map(|&child| (left_node_idx, child))
27
                .collect()
28
        }
29
    }
30
}
31

32
impl Solution for Puzzle {
33
    fn part1(&self) -> String {
34
        let mut min_dist = BinaryHeap::new();
35
        let mut search_stack = vec![(0, 0)];
36
        while let Some((left_node_idx, right_node_idx)) = search_stack.pop() {
37
            let left_node = self.octree[left_node_idx];
38
            let right_node = self.octree[right_node_idx];
39
            if let Some(&(delta, _, _)) = min_dist.peek() {
40

41
                let (left_min, left_max) = self.octree_bounding_boxes[left_node_idx];
42
                let (right_min, right_max) = self.octree_bounding_boxes[right_node_idx];
43
                let mut min_possible_dist = 0;
44
                for dim in 0..3 {
45
                    if left_max[dim] < right_min[dim] {
46
                        min_possible_dist += (right_min[dim] - left_max[dim]).pow(2);
47
                    } else if right_max[dim] < left_min[dim] {
48
                        min_possible_dist += (left_min[dim] - right_max[dim]).pow(2);
49
                    }
50
                }
51
                if min_possible_dist >= delta {
52
                    continue;
53
                }
54
            }
55

56
            if left_node.size() * right_node.size() <= self.max_steps {
57
                let pairs = if left_node_idx == right_node_idx {
58

59
                    (left_node.start..left_node.end)
60
                        .flat_map(|i| (i + 1..left_node.end).map(move |j| (i, j)))
61
                        .collect::<Vec<_>>()
62
                } else {
63

64
                    (left_node.start..left_node.end)
65
                        .flat_map(|i| (right_node.start..right_node.end).map(move |j| (i, j)))
66
                        .collect::<Vec<_>>()
67
                };
68
                for (i, j) in pairs {
69
                    let d = Self::dist(&self.nodes[i], &self.nodes[j]);
70
                    if d > min_dist.peek().map_or(i64::MAX, |&(d, _, _)| d) {
71
                        continue;
72
                    }
73
                    min_dist.push((d, i, j));
74
                    if min_dist.len() > self.max_steps {
75
                        min_dist.pop();
76
                    }
77
                }
78
                continue;
79
            }
80
            search_stack.extend(self.deeper_search_nodes(left_node_idx, right_node_idx));
81
        }
82
        let mut dsu = DisjointSet::new(self.nodes.len());
83
        for (_, i, j) in min_dist {
84
            dsu.union(i, j);
85
        }
86
        dsu.sizes
87
            .values()
88
            .fold(BinaryHeap::new(), |mut heap, &size| {
89
                heap.push(Reverse(size));
90
                if heap.len() > 3 {
91
                    heap.pop();
92
                }
93
                heap
94
            })
95
            .iter()
96
            .map(|&Reverse(x)| x)
97
            .product::<u64>()
98
            .to_string()
99
    }
100

101
    fn part2(&self) -> String {
102
        let mut dsu = DisjointSet::new(self.nodes.len());
103
        let mut last_edge = (i64::MIN, 0, 0);
104
        let mut components = vec![BTreeSet::new(); self.octree.len()];
105
        while dsu.sizes.len() > 1 {
106

107
            let mut min_edges = dsu.sizes.keys().fold(HashMap::new(), |mut map, &comp| {
108
                map.insert(comp, (i64::MAX, 0, 0));
109
                map
110
            });
111

112
            self.compute_components(&mut dsu, &mut components);
113
            let mut search_stack = vec![(0, 0)];
114
            while let Some((left_node_idx, right_node_idx)) = search_stack.pop() {
115
                let left_node = self.octree[left_node_idx];
116
                let right_node = self.octree[right_node_idx];
117

118
                if components[left_node_idx].len() == 1
119
                    && components[left_node_idx] == components[right_node_idx]
120
                {
121
                    continue;
122
                }
123

124
                let max_min_edge = components[left_node_idx]
125
                    .iter()
126
                    .chain(components[right_node_idx].iter())
127
                    .fold(i64::MIN, |max_edge, &comp| {
128
                        let Some((d, _, _)) = min_edges.get(&comp) else {
129
                            unreachable!("Every component should have an entry in min_edges")
130
                        };
131
                        max_edge.max(*d)
132
                    });
133

134
                if max_min_edge < i64::MAX {
135

136
                    let (left_min, left_max) = self.octree_bounding_boxes[left_node_idx];
137
                    let (right_min, right_max) = self.octree_bounding_boxes[right_node_idx];
138
                    let mut min_possible_dist = 0;
139
                    for dim in 0..3 {
140
                        if left_max[dim] < right_min[dim] {
141
                            min_possible_dist += (right_min[dim] - left_max[dim]).pow(2);
142
                        } else if right_max[dim] < left_min[dim] {
143
                            min_possible_dist += (left_min[dim] - right_max[dim]).pow(2);
144
                        }
145
                    }
146
                    if min_possible_dist >= max_min_edge {
147
                        continue;
148
                    }
149
                }
150

151
                if left_node.size() * right_node.size() <= 64 {
152
                    let pairs = if left_node_idx == right_node_idx {
153

154
                        let nodes = (left_node.start..left_node.end)
155
                            .map(|i| (i, dsu.find(self.nodes[i].index)))
156
                            .collect::<Vec<_>>();
157
                        nodes
158
                            .iter()
159
                            .enumerate()
160
                            .flat_map(|(idx, &i)| {
161
                                nodes[idx + 1..]
162
                                    .iter()
163
                                    .filter_map(move |&j| (i.1 != j.1).then_some((i, j)))
164
                            })
165
                            .collect::<Vec<_>>()
166
                    } else {
167

168
                        let left_nodes = (left_node.start..left_node.end)
169
                            .map(|i| (i, dsu.find(self.nodes[i].index)))
170
                            .collect::<Vec<_>>();
171
                        let right_nodes = (right_node.start..right_node.end)
172
                            .map(|i| (i, dsu.find(self.nodes[i].index)))
173
                            .collect::<Vec<_>>();
174

175
                        left_nodes
176
                            .into_iter()
177
                            .flat_map(|i| {
178
                                right_nodes
179
                                    .iter()
180
                                    .filter_map(move |&j| (i.1 != j.1).then_some((i, j)))
181
                            })
182
                            .collect::<Vec<_>>()
183
                    };
184
                    for ((i, ci), (j, cj)) in pairs {
185
                        let d = Self::dist(&self.nodes[i], &self.nodes[j]);
186
                        min_edges.entry(ci).and_modify(|entry| {
187
                            if d < entry.0 {
188
                                *entry = (d, i, j);
189
                            }
190
                        });
191
                        min_edges.entry(cj).and_modify(|entry| {
192
                            if d < entry.0 {
193
                                *entry = (d, i, j);
194
                            }
195
                        });
196
                    }
197
                    continue;
198
                }
199
                search_stack.extend(self.deeper_search_nodes(left_node_idx, right_node_idx));
200
            }
201
            for (_, (d, i, j)) in min_edges {
202
                dsu.union(self.nodes[i].index, self.nodes[j].index);
203
                if d > last_edge.0 {
204
                    last_edge = (d, i, j);
205
                }
206
            }
207
        }
208
        (self.nodes[last_edge.1].coordinate[0] * self.nodes[last_edge.2].coordinate[0]).to_string()
209
    }
210
}

总结

完整代码见此处。

通过以上分析与实现，我们成功地将解法耗时降低到 $0.75 ms$ 和 $24 ms$ ，尽管没有使用并行计算，仍然实现了 10-20 倍的性能提升。这很好地展示了利用八叉树的空间划分和分支定界策略能够有效地减少计算量，使得我们能够高效地处理点对之间的距离计算问题。当然，这种方法的实现相对复杂，需要仔细处理八叉树的构建、节点遍历以及剪枝条件等细节，这就需要根据具体的场景进行权衡和选择了。