README.md

第七回アルゴリズム実技検定 I - ほくろ

数学がわからなくてもなんとか誤魔化して通す方法

考えたこと

回転と平行移動を同時に考えることは難しいので, とりあえずどちらかを先に考えることとする.

とりあえず, 今回の問題にて特徴的である右目左目の制約 (同じ $y$ 座標を有す) を考える. 回転角度さえわかれば, 平行移動の量を求めるには, 今の座標にかかっている回転を打ち消してから, 右目左目の中心点を原点に動かすだけの量を考えればよいな, として角度を先に求めたい気持ちになる.

他者の AC コードを見ると, 公式解説の複素数を使わずとも, $atan$ を用いて回転角度を一発で算出している人が多い. たしかにそれは正しい方針っぽい. だが, 私は数学がよくわからないので, そこまで思い至らず, 二分探索で誤魔化せないかという方針に進んでしまった.

両目の $y$ 座標を一致させるには, 今の原点を中心として適当に回転してやればよい. 回転させる角度は $[0, 360)$ の区間に絞れるし, 回転後の両目の $y$ 座標の差には 直感的には 連続性があるような気がした (本当に？). ので, とりあえず, 左目の $y$ 座標から右目の $y$ 座標を引いた値が 0.0 に十分近くなる角度 $\theta$ を二分探索して求めた.

ここで, $y$ 座標の差を絶対値で取ると多分 WA になる. というのは, 差の絶対値が 0 となる地点は二箇所あるためである

---

$y$ 座標の差はサインカーブみたいになりそうだけど, これでなんで求まるのだろう.

i.rs

use proconio::input;

fn main() {
    input! {
        n: usize,
        xy2: [(f64, f64); 2],
        abn: [(f64, f64); n],
    }

    // ようわからんからとりあえず角度を二分探索してみる
    let mut deg_min = 0.0f64;
    let mut deg_max = 360.0f64;
    let mut cnt = 0;
    while (deg_max - deg_min) > 1e-10 && cnt < 100_000 {
        let mid = (deg_max + deg_min) / 2.0;
        let cos_r = (mid * std::f64::consts::PI / 180.0).cos();
        let sin_r = (mid * std::f64::consts::PI / 180.0).sin();

        let y0 = xy2[0].0 * sin_r + xy2[0].1 * cos_r;
        let y1 = xy2[1].0 * sin_r + xy2[1].1 * cos_r;

        if y1 - y0 > 0.0 {
            deg_max = mid;
        } else {
            deg_min = mid;
        }
        cnt += 1;
    }

    let cos_r = (deg_max * std::f64::consts::PI / 180.0).cos();
    let sin_r = (deg_max * std::f64::consts::PI / 180.0).sin();
    let x0 = xy2[0].0 * cos_r - xy2[0].1 * sin_r;
    let x1 = xy2[1].0 * cos_r - xy2[1].1 * sin_r;
    let y0 = xy2[0].0 * sin_r + xy2[0].1 * cos_r;
    let par_move_x = -(x0 + x1) / 2.0;
    let par_move_y = -y0;

    for ab in abn {
        let cos_r = (deg_max * std::f64::consts::PI / 180.0).cos();
        let sin_r = (deg_max * std::f64::consts::PI / 180.0).sin();
        let xx = ab.0 * cos_r - ab.1 * sin_r + par_move_x;
        let yy = ab.0 * sin_r + ab.1 * cos_r + par_move_y;
        println!("{} {}", xx, yy);
    }
}