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

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代码

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