D - 地図が2枚

Quiz

https://atcoder.jp/contests/utpc2012/tasks/utpc2012_04

Submission

https://atcoder.jp/contests/utpc2012/submissions/5719321

解法

  • 点(a, b)が点(b, c)に縮小・回転・移動されている
  • 縮小・回転は複素数の掛け算・割り算、平行移動は複素数の和・差で求まる
  • (a, b) -> (c, d)に移す変換を求めたら、その変換を(c, d)に適用して(e, f)を求め、収束するまで続ける

精度不足

想定解?

  • 想定解は不動点を方程式の解からO(1)で求まる方法だろう
  • そちらの方が誤差にも強いだろう

複素数でアフィン変換

  • 原点に移動して回転、これだけなのだが中々苦労した

Note

f:id:peroon:20190601142226j:plain