2022-11-06：给定平面上n个点，x和y坐标都是整数，
找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的。
返回最短距离，精确到小数点后面4位。
答案2022-11-06：
暴力法是的复杂度是O(N**2)。
跟归并排序类似。T(N) = 2*T(N/2) O(N)。网上很多算法的复杂度是O(N*(logN)的平方)。
时间复杂度：O(N*logN)。
代码用rust编写。代码如下：
代码语言：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代码
