B - アリの高橋くん arc042_b 「線分と点の距離」を複素数で (二次元)

Quiz

https://atcoder.jp/contests/arc042/tasks/arc042_b

Submit

https://atcoder.jp/contests/arc042/submissions/4201752

Note

• (追記：この記事には考慮漏れがあります）
• 各線分と点の距離を求めればいい
• 複素平面上で考える
• editorialの通り、c2 - c1からなるベクトルの偏角を0にするようにPを回転する
• 複素数において、
  • かけ算は反時計回り
  • よって時計回りにしたいときは割り算をすればいい
• スケールは変えたくないので単位ベクトルで割る
• Pを回転させたあとのy (imag) が点と線分の距離 d である

• 回転のイメージは画像の左側に描いてある
• しかし、画像右のような場合はどうだろう、上記方法では間違った距離が求まってしまう
• 赤線で描いた距離を返すのが正しい

typedef complex<double> cd;
 
double distance(cd p0, cd c1, cd c2){
    // c1原点に移動
    p0 -= c1;
    c2 -= c1;
 
    // 回転
    auto u = c2 / abs(c2);
    p0 /= u;
 
    return p0.imag();
}