haar_lib/geom_int/
closest_pair.rs

1//! 最近点対
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/closest_pair>
5
6use crate::chmin;
7use crate::{algo::merge::*, geom_int::*};
8
9/// 最近点対を求める。
10pub fn closest_pair(ps: Vec<VectorInt>) -> Option<((usize, VectorInt), (usize, VectorInt))> {
11    if ps.len() < 2 {
12        None
13    } else {
14        let mut ps: Vec<_> = ps.into_iter().enumerate().collect();
15        ps.sort_by(|(_, p), (_, q)| p.x.cmp(&q.x));
16        rec(&mut ps)
17    }
18}
19
20fn rec(ps: &mut [(usize, VectorInt)]) -> Option<((usize, VectorInt), (usize, VectorInt))> {
21    let n = ps.len();
22    match n {
23        0 => unreachable!(),
24        1 => None,
25        2 => {
26            if ps[0].1.y > ps[1].1.y {
27                ps.swap(0, 1);
28            }
29            Some((ps[0], ps[1]))
30        }
31        _ => {
32            let mid_x = ps[n / 2].1.x;
33            let (left, right) = ps.split_at_mut(n / 2);
34            let d1 = rec(left);
35            let d2 = rec(right);
36
37            inplace_merge_by(ps, n / 2, |a, b| a.1.y < b.1.y);
38
39            let mut d = i64::MAX;
40            let mut ret = None;
41
42            if let Some((p, q)) = d1 {
43                let t = (p.1 - q.1).abs_sq();
44                if chmin!(d, t) {
45                    ret = Some((p, q));
46                }
47            }
48            if let Some((p, q)) = d2 {
49                let t = (p.1 - q.1).abs_sq();
50                if chmin!(d, t) {
51                    ret = Some((p, q));
52                }
53            }
54
55            let mut v: Vec<(usize, VectorInt)> = vec![];
56
57            for &mut p in ps {
58                let t = (p.1.x - mid_x).abs();
59                if t * t >= d {
60                    continue;
61                }
62
63                for &q in v.iter().rev() {
64                    let t = (p.1.y - q.1.y).abs();
65                    if t * t >= d {
66                        break;
67                    }
68
69                    let t = (p.1 - q.1).abs_sq();
70                    if chmin!(d, t) {
71                        ret = Some((p, q));
72                    }
73                }
74
75                v.push(p);
76            }
77
78            ret
79        }
80    }
81}
haar_lib/geom_int/closest_pair.rs

haar_lib/geom_int/
closest_pair.rs
