D - 地図が２枚

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)を求め、収束するまで続ける

精度不足

• long doubleでは精度が足りなかった
  • https://atcoder.jp/contests/utpc2012/submissions/5719113
  • WAのみ消費時間が長い
• そこで、boostでさらに精度を上げたらACした

想定解？

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

複素数でアフィン変換

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

Note