bouzuya.hatenablog.com

ぼうずやのにっき

子どもが嘔吐して 1 回休み / PAST#6 L

子どもが嘔吐して 1 回休み。

長袖シャツをすべて捨てた。もうすこしシンプルにしたい。

『初めての GraphQL 』を読んだ。初めてではない。 ISUCON 本は？

use dsu::*;
use proconio::input;

fn dist((px_i, py_i): (i64, i64), (px_j, py_j): (i64, i64)) -> f64 {
    (((px_i - px_j).pow(2) + (py_i - py_j).pow(2)) as f64).sqrt()
}

fn kruskal(n: usize, e: &mut [(usize, usize, f64)]) -> f64 {
    e.sort_by(|(_, _, w1), (_, _, w2)| w1.partial_cmp(w2).unwrap());
    let mut dsu = Dsu::new(n);
    let mut sum = 0_f64;
    for (u_i, v_i, w_i) in e.iter().copied() {
        if !dsu.same(u_i, v_i) {
            dsu.merge(u_i, v_i);
            sum += w_i;
        }
    }
    sum
}

fn main() {
    input! {
        n: usize,
        m: usize,
        p: [(i64, i64); n],
        cr: [(i64, i64, i64); m],
    }

    let mut edges = vec![vec![]; n];
    for (i, p_i) in p.iter().copied().enumerate() {
        for (j, p_j) in p.iter().copied().enumerate() {
            if i == j {
                continue;
            }
            edges[i].push((j, dist(p_i, p_j)));
        }
    }

    let mut min = 1e18;
    for bits in 0..1 << m {
        let cr = cr
            .iter()
            .copied()
            .enumerate()
            .filter(|(i, _)| ((bits >> i) & 1) == 1)
            .map(|(_, (x, y, r))| (x, y, r))
            .collect::<Vec<_>>();
        let m = cr.len();
        let edges = {
            let mut e = vec![vec![]; n + m];
            for (i, edges_i) in edges.iter().enumerate() {
                e[i] = edges_i.clone();
            }
            for (i, p_i) in p.iter().copied().enumerate() {
                for (j, (cx_j, cy_j, r_j)) in cr.iter().copied().enumerate() {
                    let d = (dist(p_i, (cx_j, cy_j)) - r_j as f64).abs();
                    e[i].push((n + j, d));
                    e[n + j].push((i, d));
                }
            }
            for (i, (cx_i, cy_i, r_i)) in cr.iter().copied().enumerate() {
                for (j, (cx_j, cy_j, r_j)) in cr.iter().copied().enumerate() {
                    if i == j {
                        continue;
                    }
                    let d = (((cx_i - cx_j).pow(2) + (cy_i - cy_j).pow(2)) as f64).sqrt();
                    let r1 = (r_i + r_j) as f64;
                    let r2 = (r_i - r_j).abs() as f64;
                    let d = if r1 <= d {
                        d - (r_i + r_j) as f64
                    } else if r2 < d {
                        0.0
                    } else {
                        r2 - d
                    };
                    e[n + i].push((n + j, d));
                }
            }
            e
        };

        let mut edges = {
            let mut e = vec![];
            for (i, jd) in edges.into_iter().enumerate() {
                for (j, d) in jd {
                    e.push((i, j, d));
                }
            }
            e
        };

        let min_cost = kruskal(n + m, &mut edges);
        if min_cost < min {
            min = min_cost;
        }
    }

    println!("{}", min);
}

// dsu

今日のコミット。