アルゴリズムと数学 103

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bw

点数がつくだけなのでどうやってもいいですが、正六角形上に並べた方が正方形に並べるよりは効率がよいので、中心を適当に変えて100個並べられて最も大きな半径を求めます。
よく考えたら、周りから埋めていったほうがよさそうですね。

// Circle Packing
#![allow(non_snake_case)]


//////////////////// library ////////////////////


//////////////////// Point ////////////////////

use std::ops::{Add, Mul};

#[derive(Clone, Copy)]
struct Point<T: Add<Output = T> + Copy> {
    x: T,
    y: T
}

impl<T: Add<Output = T> + Copy> Add for Point<T> {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl<T: Add<Output = T> + Mul<Output = T> + Copy> Mul<T> for Point<T> {
    type Output = Self;
    
    fn mul(self, c: T) -> Self {
        Self { x: self.x * c, y: self.y * c }
    }
}

impl <T: Add<Output = T> + Mul<Output = T> + Copy> Point<T> {
    fn new(x: T, y: T) -> Point<T> {
        Point { x, y }
    }
    
    fn mag2(&self) -> T {
        self.x * self.x + self.y * self.y
    }
}


//////////////////// process ////////////////////

fn is_inner(pt: Point<f64>, r: f64) -> bool {
    pt.mag2().sqrt() + r <= 1.0
}

fn F_j<T: Iterator<Item=i32>>(it: T, i: i32, r: f64,
                                    c: Point<f64>) -> Vec<Point<f64>> {
    let v1 = Point::new(1.0, 0.0);
    let v2 = Point::new(1.0, 3.0_f64.sqrt()) * 0.5;
    let mut cs: Vec<Point<f64>> = vec![];
    for j in it {
        let pt = c + (v1 * (i as f64) + v2 * (j as f64)) * (r*2.0);
        if is_inner(pt, r) {
            cs.push(pt)
        }
        else {
            break
        }
    }
    cs
}

fn F_offset_center(r: f64, c: Point<f64>) -> Vec<Point<f64>> {
    let mut cs: Vec<Point<f64>> = vec![];
    for i in 0.. {
        let mut cs1 = F_j(0.., i, r, c);
        let cs2 = F_j((1..).map(|j| - j), i, r, c);
        cs1.extend(&cs2);
        if cs1.is_empty() {
            break
        }
        cs.extend(&cs1)
    }
    for i in (1..).map(|i| -i) {
        let mut cs1 = F_j(0.., i, r, c);
        let cs2 = F_j((1..).map(|j| - j), i, r, c);
        cs1.extend(&cs2);
        if cs1.is_empty() {
            break
        }
        cs.extend(&cs1)
    }
    cs
}

// 何個積めるか
fn F_each(r: f64) -> Vec<Point<f64>> {
    (0..10).
    flat_map(|i| (0..10).map(move |j| Point::<f64>::new(
                                        (i as f64)*r*0.1, (j as f64)*r*0.1))).
    map(|c| F_offset_center(r, c)).max_by_key(|v| v.len()).unwrap()
}

fn bin_search(first: f64, last: f64, N: usize) -> f64 {
    if last - first < 1e-6 {
        first
    }
    else {
        let mid = (first + last) / 2.0;
        let cs = F_each(mid);
        if cs.len() >= N {
            bin_search(mid, last, N)
        }
        else {
            bin_search(first, mid, N)
        }
    }
}

fn print_centers(cs: Vec<Point<f64>>) {
    for i in 0..100 {
        println!("{} {}", cs[i].x, cs[i].y)
    }
}

fn F(N: usize) {
    let r = bin_search(0.07, 0.1, N);
    let cs = F_each(r);
    print_centers(cs)
}

fn main() {
    F(100)
}