Closest Moment の解説

• スタート ~ どちらかが止まるまで
• どちらかが止まるまで ~ 両方止まるまで

の二つの区間で最小値を求める関数が異なるのでわけて考える。

普通に距離は二次関数になるので、解析的に解けるが、脳死で三分探索することで思考をサボれる。

fn solve(i: usize) {
    input! {
        tsx: f64,
        tsy: f64,
        tgx: f64,
        tgy: f64,
        asx: f64,
        asy: f64,
        agx: f64,
        agy: f64,
    }
    let dist = |x: (f64, f64), y: (f64, f64)| {
        let (x1, y1) = x;
        let (x2, y2) = y;
        let d2 = (x2 - x1).powi(2) + (y2 - y1).powi(2);
        d2.sqrt()
    };
    let f = |start: (f64, f64), goal: (f64, f64), time: f64| {
        let d = dist(start, goal);
        if d <= time {
            return goal;
        }
        let rate = time / d;
        let (sx, sy) = start;
        let (gx, gy) = goal;
        let xdiff = gx - sx;
        let ydiff = gy - sy;

        let x = sx + xdiff * rate;
        let y = sy + ydiff * rate;
        (x, y)
    };
    let f2 = |time: f64| {
        let tnow = f((tsx, tsy), (tgx, tgy), time);
        let anow = f((asx, asy), (agx, agy), time);
        dist(tnow, anow)
    };
    let tt = dist((tsx, tsy), (tgx, tgy));
    let at = dist((asx, asy), (agx, agy));
    let v = vec![(0., tt.min(at)), (tt.min(at), tt.max(at))];

    let mut ans = f64::MAX;
    for &(mut left, mut right) in v.iter() {
        while right - left > 10f64.powi(-7) {
            let diff = (right - left) / 3.;
            let ll = left + diff;
            let rr = left + diff * 2.;
            let lans = f2(ll);
            let rans = f2(rr);
            if lans < rans {
                right = rr;
            } else {
                left = ll;
            }
        }
        let a = {
            let a1 = f((tsx, tsy), (tgx, tgy), left);
            let a2 = f((asx, asy), (agx, agy), left);
            dist(a1, a2)
        };
        ans = ans.min(a);
    }
    println!("{}", ans);
}