competitive/geometry/
closest_pair.rs

1use super::{Complex, TotalOrd};
2
3pub fn closest_pair(a: Vec<Complex<f64>>) -> f64 {
4    let mut a = a;
5    a.sort_by_key(|&p| TotalOrd(p.re));
6    closest_pair_inner(&mut a[..])
7}
8fn closest_pair_inner(a: &mut [Complex<f64>]) -> f64 {
9    use std::cmp::min;
10    let n = a.len();
11    if n <= 1 {
12        return f64::INFINITY;
13    }
14    let m = n / 2;
15    let x = a[m].re;
16    let mut d = min(
17        TotalOrd(closest_pair_inner(&mut a[0..m])),
18        TotalOrd(closest_pair_inner(&mut a[m..n])),
19    )
20    .0;
21    a.sort_by_key(|&p| TotalOrd(p.im));
22    let mut b: Vec<Complex<f64>> = vec![];
23    for a in a.iter() {
24        if (a.re - x).abs() >= d {
25            continue;
26        }
27        let k = b.len();
28        for j in 0..k {
29            let p = *a - b[k - j - 1];
30            if p.im >= d {
31                break;
32            }
33            d = min(TotalOrd(d), TotalOrd(p.abs())).0;
34        }
35        b.push(*a);
36    }
37    d
38}
competitive/geometry/closest_pair.rs

competitive/geometry/
closest_pair.rs
