ABC022 D - Big Bang
解法
それぞれの操作をどのように実行したかを求めるのは、とてつもなく難しそうです。
ので、他の方法で高速に答えを求める方法を探ります。
そのためには、平行移動と回転の操作では変化せず、拡大したときのみ変化する部分が必要になります。
ということで、これを探すと、まず
- それぞれの頂点間の距離
が見つかります。
よって、全ての頂点間の距離を1つ1つ求め、操作前と操作後のそれぞれ最大値を比較すると、その倍率がそのものになります。
ですが、頂点間の距離1つ1つを求めるのには時間がかかります(一応最短距離を高速に導く方法もあるみたいなので、そちらを実装すれば通るみたいです)。これでは部分点しかとることができません。
ということで、もう少し探していると、
頂点の重心からそれぞれの頂点への距離
もまた、最後の操作でのみ倍される距離になることがわかります。
よって、重心は個の頂点についてそれぞれの座標を合計し、
で割ることで求められるため、ここからの距離を
頂点について計算、そして操作前後の重心からの最長距離を計算すれば、その倍率が答えになります。
感想
一見どこから手を付ければいいのかわからない問題でした。ので、何か簡単に求められる方法があるのだろうということで探していくと、上のような方法が思い浮かびました。
1つめはすんなり出てきましたが、満点解法についてはかなりの時間を要しました(半日～1日)。
難しいですね…
