Hide

Problem C
アムステルダムでの道のり

Languages en ja

アムステルダムに住んでいるあなたのもとに、マンハッタンから友人が来た。彼女は短期間の滞在なので、多くの観光スポットをできるだけ時間を掛けずに周りたい。そのため、彼女は観光スポット間の距離を知りたがっている。彼女の地元のマンハッタンではこれは簡単で、地点 $m = (m_ x, m_ y)$ から地点 $n = (n_ x, n_ y)$ までの距離は、

\[ |n_ x - m_ x| + |n_ y - m_ y|, \]

で求められる。これは、マンハッタンの道路は碁盤の目状に通っているためだ。しかし、アムステルダムでは事情が異なる。したがって、あなたはアムステルダムにおける最短距離の計算方法を導き出す必要がある。アムステルダムの道路は半円状になっており、中央から一定の角度で放射状に延びた道と、等間隔の運河に沿った半円形の道がある。 それらの道が交わるところがそれぞれ交差点となる。

\includegraphics[width=0.75\textwidth ]{image.pdf}
図 1: サンプル入力1

アムステルダムの街路図をモデル化する精度に基づいて、都市を半円に分割するサイズが異なる。さらに、変換の際の問題を避けるため、半円の半径として与えられた任意の単位で動作するプログラムを作成することとする。 2つの交差点間の距離を求めるプログラムを作ることで、あなたは友人を手伝うことができるだろうか。

入力

入力は以下の形式で与えられる。

  • 先頭行は $2$ つの整数 $M,N$ と実数 $R$ を含む。

    • $M$$1 \leq M \leq 100$ で、街を分割するセグメント(扇型)の数を示す。

    • $N$$1 \leq N \leq 100$ で、円周によって街を分割する数を示す。

    • $R$$1 \leq R \leq 1000$ で、街の半径を示し、小数点以下最大 $15$ 桁までで与えられる。

  • の行は $4$ つの整数 $a_ x, a_ y, b_ x, b_ y$ で、 $0 \leq a_ x, b_ x \leq M$$0 \leq a_ y, b_ y \leq N$, であり、アムステルダムのモデル上での2点の座標を表す。

出力

単一の実数を含む単一行を出力する。これは、与えられた2点を結ぶ最短の道のりを表す。結果の誤差は、絶対・相対で $10^{-6}$ 以下とすること。

サンプル入力 1 サンプル出力 1
6 5 2.0
1 3 4 2
1.65663706143592
サンプル入力 2 サンプル出力 2
9 7 3.0
1 5 9 5
4.28571428571429
サンプル入力 3 サンプル出力 3
10 10 1.0
2 0 6 0
0