2022-11-06：给定平面上n个点，x和y坐标都是整数， 找出其中的一对点的距离，使得在这n个点

2022-11-06：给定平面上n个点，x和y坐标都是整数， 找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。 返回最短距离，精确到小数点后面4位。

答案2022-11-06：

暴力法是的复杂度是O(N**2)。 跟归并排序类似。T(N) = 2T(N/2) + O(N)。网上很多算法的复杂度是O(N(logN)的平方)。 时间复杂度：O(N*logN)。

代码用rust编写。代码如下：

use std::iter::repeat;

fn main() {
    unsafe {
        let input: [i32; 7] = [3, 1, 1, 1, 2, 2, 2];
        let mut input_index = 0;
        let n = input[input_index];
        // N = n as usize;
        input_index += 1;
        points = repeat(Point::new(0.0, 0.0)).take(n as usize).collect();
        merge = repeat(Point::new(0.0, 0.0)).take(n as usize).collect();
        deals = repeat(Point::new(0.0, 0.0)).take(n as usize).collect();
        for i in 0..n {
            let x = input[input_index];
            input_index += 1;
            let y = input[input_index];
            input_index += 1;
            points[i as usize].x = x as f64;
            points[i as usize].y = y as f64;
        }
        points.sort_by(|a, b| {
            if a.x <= b.x {
                core::cmp::Ordering::Less
            } else {
                core::cmp::Ordering::Greater
            }
        });
        let ans = nearest(0, n - 1);
        println!("{:.4}", ans);
    }
}

static mut points: Vec<Point> = vec![];
static mut merge: Vec<Point> = vec![];
static mut deals: Vec<Point> = vec![];

#[derive(Debug, Copy, Clone)]
struct Point {
    x: f64,
    y: f64,
}

impl Point {
    fn new(a: f64, b: f64) -> Self {
        Self { x: a, y: b }
    }
}

fn nearest(left: i32, right: i32) -> f64 {
    unsafe {
        let mut ans = f64::MAX;
        if (left == right) {
            return ans;
        }
        let mut mid = (right + left) / 2;
        let mid_x = points[mid as usize].x;
        ans = get_min(nearest(left, mid), nearest(mid + 1, right));
        let mut p1 = left;
        let mut p2 = mid + 1;
        let mut merge_size = left;
        let mut deal_size = 0;
        while (p1 <= mid && p2 <= right) {
            if points[p1 as usize].y <= points[p2 as usize].y {
                merge[merge_size as usize] = points[p1 as usize];
                p1 += 1;
            } else {
                merge[merge_size as usize] = points[p2 as usize];
                p2 += 1;
            }
            if (f64::abs(merge[merge_size as usize].x - mid_x) <= ans) {
                deals[deal_size as usize] = merge[merge_size as usize];
                deal_size += 1;
            }
            merge_size += 1;
        }
        while (p1 <= mid) {
            merge[merge_size as usize] = points[p1 as usize];
            p1 += 1;
            if (f64::abs(merge[merge_size as usize].x - mid_x) <= ans) {
                deals[deal_size as usize] = merge[merge_size as usize];
                deal_size += 1;
            }
            merge_size += 1;
        }
        while (p2 <= right) {
            merge[merge_size as usize] = points[p2 as usize];
            p2 += 1;
            if (f64::abs(merge[merge_size as usize].x - mid_x) <= ans) {
                deals[deal_size as usize] = merge[merge_size as usize];
                deal_size += 1;
            }
            merge_size += 1;
        }
        for i in left..=right {
            points[i as usize] = merge[i as usize];
        }
        for i in 0..deal_size {
            for j in i + 1..deal_size {
                if (deals[j as usize].y - deals[i as usize].y >= ans) {
                    break;
                }
                ans = get_min(
                    ans,
                    distance(&mut deals[i as usize], &mut deals[j as usize]),
                );
            }
        }
        return ans;
    }
}

fn distance(a: &mut Point, b: &mut Point) -> f64 {
    let x = a.x - b.x;
    let y = a.y - b.y;
    return f64::sqrt(x * x + y * y);
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a < b {
        a
    } else {
        b
    }
}

执行结果如下：

左神java代码