目录
题目地址
https://ac.nowcoder.com/acm/contest/52826/C
代码
use std::io;
use std::cmp::Ordering;
use std::f64;
#[derive(Debug, PartialEq, PartialOrd, Clone, Copy)]
struct Point {
x: f64,
y: f64,
}
fn euclidean_distance(p1: &Point, p2: &Point) -> f64 {
let dx = p1.x - p2.x;
let dy = p1.y - p2.y;
(dx * dx + dy * dy).sqrt()
}
fn brute_force(points: &[Point]) -> f64 {
let mut min_distance = f64::INFINITY;
for i in 0..points.len() {
for j in (i + 1)..points.len() {
let dist = euclidean_distance(&points[i], &points[j]);
min_distance = min_distance.min(dist);
}
}
min_distance
}
fn strip_closest(strip: &mut [Point], d: f64) -> f64 {
strip.sort_by(|a, b| a.y.partial_cmp(&b.y).unwrap_or(Ordering::Equal));
let mut min_distance = d;
for i in 0..strip.len() {
let mut j = i + 1;
while j < strip.len() && (strip[j].y - strip[i].y) < min_distance {
min_distance = min_distance.min(euclidean_distance(&strip[i], &strip[j]));
j += 1;
}
}
min_distance
}
fn closest_points_distance(points: &[Point]) -> f64 {
if points.len() <= 3 {
return brute_force(points);
}
let mid = points.len() / 2;
let mid_point = points[mid];
let dl = closest_points_distance(&points[..mid]);
let dr = closest_points_distance(&points[mid..]);
let mut d = dl.min(dr);
let strip: Vec<Point> = points
.iter()
.filter(|point| (point.x - mid_point.x).abs() < d)
.cloned()
.collect();
d = d.min(strip_closest(&mut strip.clone(), d));
d
}
fn main() {
let stdin = io::stdin();
let mut buffer = String::new();
stdin.read_line(&mut buffer).unwrap();
let test_cases: u32 = buffer.trim().parse().unwrap();
for _ in 0..test_cases {
buffer.clear();
stdin.read_line(&mut buffer).unwrap();
let n: usize = buffer.trim().parse().unwrap();
let mut points = Vec::with_capacity(n);
for _ in 0..n {
buffer.clear();
stdin.read_line(&mut buffer).unwrap();
let coords: Vec<f64> = buffer
.trim()
.split_whitespace()
.map(|x| x.parse().unwrap())
.collect();
points.push(Point { x: coords[0], y: coords[1] });
}
points.sort_by(|a, b| a.x.partial_cmp(&b.x).unwrap_or(Ordering::Equal));
let result = closest_points_distance(&points);
println!("{:.0}", result * result);
}
}
标签:distance,min,mut,距离,最近,let,strip,Rust,points
From: https://www.cnblogs.com/yhm138/p/17297135.html