時間制限:1000ミリ秒
メモリ制限:10000KB
振り子の周期
問題
壁のフックに掛けられた振り子を考える。振り子が押されると、行ったり戻ったりする。ここで壁に他のフックがあり、振り子の経路上にあることを考える。振り子はその点で曲がり、もしかしたらその点を中心に周り続けるかもしれない。一般に、これはもとより非常に複雑な経路を描く。ある程度経過すると、振り子の動きは繰り返しはじめ、周期的な動きをし始める。私たちがやりたいことは、振り子が1周期を描くまでに移動した距離を計算することである。
より形式的に定義するため、壁に直交座標を定義する。振り子の片側は原点(0,0)に固定されている。一般的に用いられるように、X軸は右方向を向き、Y軸は上方向を向く。振り子のひもの長さはrである。振り子は(-r,0)の位置で離され、右方向に振りだす。平面上には他にn個のフックがあり、振り子の経路に影響を与えることがある。
ここでは理想的な世界として、以下の想定は正しいとする:
- フックと振り子のひもの直径はどちらも0とする。
- 振り子はエネルギーを失うことはない(摩擦などで)。
- 振り子本体はフックに当たることはなく、そのひものみがフックに当たる。
- 振り子の糸はある先進的な材質でできていて、フックに当たったところは曲がるが、そうでない場所ではまっすぐである。
あなたのプログラムは、振り子の動きをシミュレートして、振り子が最終的に入る周期の空間的な長さを出力する必要がある。物理の知識からわかるように、振り子は初期位置より高い位置に到達することはない!つまり、X軸より上に来ることはない。振り子は最初の高さに到達するか、いずれかのフックの周囲を終わりなく周り続けるかのどちらかである。
入力
入力はいくつかのテストケースからなる。各ケースの最初の行は整数n(フックの数、1 <= n < 500)と実数r(振り子のひもの長さ)の2数が空白を区切りとして書かれている。続くn行は対応するフックのx座標とy座標をあらわす2つの整数が空白を区切りとして書かれている。
入力はr=0なケースをもって終了とする。このケース自身は処理しないこと。
出力
各ケースについて、まずテストケースの番号をあらわす1行を出力せよ。('Pendulum #1', 'Pendulum #2' など)
続いて、振り子が周期を完全に1周する間の距離を含む1行を出力せよ。周期に到達するまでの距離は数えない。(フォーマットは出力例を参照のこと。)距離は小数点以下2桁まで一致しなければならない。
各テストケースの後には空行を出力すること。
入力例
2 16.0 3 -4 -3 -4 1 18.0 5 -12 0 0
出力例
Pendulum #1 Length of periodic orbit = 87.66
Pendulum #2 Length of periodic orbit = 31.42
出典
Southwestern European Regional Contest 1996