No.3042 拡大コピー
タグ : / 解いたユーザー数 47
作問者 :


問題文
以下で出てくる写真は長方形になっており、左下の角を原点としてそこから写真の端に沿って
右に$x$座標をとり、上に$y$座標をとることとします。座標は$mm$単位になっているとします。
星の写真があります。そこには、
$N$
個の星があり、それらの位置は
$(x_i, y_i) ~ (1 \le i \le N)$
となっています。
その写真を別の大きな白い紙にはみ出さないように貼り付けました。
このとき、貼り付ける向きと位置をとても適当に貼り付けてしまいました。
白い紙をコピー機で拡大コピー(縮小もあり得る)して写真にしました。
すると星の位置は、最初の順番と一致しているとは限りませんが、
$(z_j, w_j) ~ (1 \le j \le N)$
となりました。
何倍にコピーしましたか。$10^{-3}$未満の絶対誤差は許容されます。
ただしコピーとは、白い紙の左下の角を中心に相似拡大しているとします。
入力
$N$ $x_1\ y_1$ . . . $x_N\ y_N$ $z_1\ w_1$ . . . $z_N\ w_N$
$2 \le N \le 10^6$
$x_i, y_i, z_j, w_j ~ (1 \le i \le N, 1 \le j \le N)$
は小数です。
$(x_i, y_i) \neq (x_j, y_j) ~ (i \neq j)$
$0 \le x_i, y_i, z_j, w_j \le 10^9 ~ (1 \le i \le N, 1 \le j \le N)$
$(x_i, y_i)$が$(z_i, w_i)$に移動しているとは限りません。
出力
ans最後に改行してください。
サンプル
サンプル1
入力
2 1 1 2 2 4 4 2 2
2
$(1, 1)$が$(2, 2)$に対応しており$(2, 2)$が$(4, 4)$に対応していると考えると、写真と白い紙の左下が一致するように貼って、$2$倍コピーしたと考えることができます。 この例のように入力の順番でコピー先が一致しているとは限らないので注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。