首页 > 其他分享 >【计算几何】Rust求解平面最近点对(寻找距离最近的两个点的距离)

【计算几何】Rust求解平面最近点对(寻找距离最近的两个点的距离)

时间:2023-05-14 16:35:23浏览次数:47  
标签:distance min mut 距离 最近 let strip Rust points

目录

题目地址

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

相关文章

  • 基于车速的变预测时域的MPC自适应轨迹跟踪控制,能够预测时域的, 类似驾驶员模型中的预
    基于车速的变预测时域的MPC自适应轨迹跟踪控制,能够预测时域的,类似驾驶员模型中的预瞄距离,在不同的车速下,预瞄控制器采用不同预瞄距离产生的控制效果不同,通过carsim与simulink联合仿真结果发现,改进后的轨迹跟踪控制器既满足了车辆低速行驶下的轨迹跟踪精度,也一定程度上克服了高速......
  • 5辆车组成的编队实现ACC自适应协同控制,通过考虑前车的加速度和距离,实现自适应巡航控制
    5辆车组成的编队实现ACC自适应协同控制,通过考虑前车的加速度和距离,实现自适应巡航控制,仿真平台基于carsim/Simulink实现。算法结构分为两层,上层滑膜控制器差生期望的加速度,下层通过控制节气门开度和刹车制动压力控制车速。仿真结果图给出了5辆车前车与后车的跟踪误差、5辆车车速的......
  • 台达PLC-EH3.铆压机,3轴,Z轴(SMC)电缸下降的距离用的是位置加扭矩模式,台达PLC MODBUS通
    台达PLC-EH3.铆压机,3轴,Z轴(SMC)电缸下降的距离用的是位置加扭矩模式,台达PLCMODBUS通讯控制台达A2伺服扭矩,自动上下料,每个点位可跳点,可设位置和扭矩,PLC程序有完整的注释,触摸屏程序,伺服参数设定程序.电气BOM.电气CAD图纸。ID:6620665415434852......
  • 台达PLC-EH3.铆压机,3轴,Z轴(SMC)电缸下降的距离用的是位置加扭矩模式,台达PLC MODBUS通
    台达PLC-EH3.铆压机,3轴,Z轴(SMC)电缸下降的距离用的是位置加扭矩模式,台达PLCMODBUS通讯控制台达A2伺服扭矩,自动上下料,每个点位可跳点,可设位置和扭矩,PLC程序有完整的注释,触摸屏程序,伺服参数设定程序.电气BOM.电气CAD图纸。ID:3618670233899230......
  • 聊一聊最近高速发展的ChatGPT
     随着人工智能技术的不断发展和普及,ChatGPT作为聊天机器人的代表之一也在不断发展和壮大。未来,ChatGPT将有以下几个方面的发展趋势:语义理解和智能对话的提升:ChatGPT将会不断提高语义理解和智能对话的能力,通过学习用户的习惯和使用方式,逐步提高机器人的智能水平,使其成为一名......
  • Delta/台达PLC-EH3铆压机程序。 3轴,Z轴(SMC)电缸下降的距离用的
    Delta/台达PLC-EH3铆压机程序。3轴,Z轴(SMC)电缸下降的距离用的是位置加扭矩模式,台达PLCMODBUS通讯控制台达A2伺服扭矩,自动上下料,每个点位可跳点,可设位置和扭矩,PLC程序有完整的注释,触摸屏程序,伺服参数设定程序.电气BOM.电气CAD图纸。ID:7913668623547852......
  • 最近VJ刷题整理
    BitsReverse题意:给出两个数,每次操作其中一个数,将其二进制位上连续的三个数翻转,求最小的操作次数Solution每次操作相当于交换了左右两个二进制位的数,所以一次操作只会改变奇数位/偶数位上的数,考虑到只用求最小的操作次数,我们可以将每个数的二进制位上的1所在的位置分奇偶存一下......
  • 实现导航栏固定,滚动条下滑一定距离后消失,上划继续出现
    实现导航栏固定,滚动条下滑一定距离后消失,上划继续出现constshowHeader=ref(true);//获取滚动条的高度constgetScrollTop=()=>{letscrollTop=document.documentElement.scrollTop||window.pageYOffset||document.body.scrollTop;returnscr......
  • 两个数组间的距离值
    给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。「距离值」 定义为符合此距离要求的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足|arr1[i]-arr2[j]|<=d。示例1:输入:arr1=[4,5,8],arr2=[10,9,1,8],d=2输出:2......
  • Rust 笔记
    TheRustProgrammingLanguageRust编程语言笔记。来源:TheRustProgrammingLanguageBook。安装使用rustup来安装Rust。Rust源文件以.rs作为扩展名。几个常用的命令:编译:rustc.rs-file运行:./compiled-file检查Rust编译器版本:rustc--version检查rustup......