1

SPOJ のようなプラットフォームから解決しなければならない問題がありますが、これを解決する方法が思いつきません。G トランスレータで翻訳された問題は次のとおりですが、何かが失われた場合は、より良い翻訳を試みることができます

このエントリは、テスト数 T (10 <= T <= 100) を示します。各テストに対して、数値 N (3 <= N <= 100) を指定します。この数は、一辺が 1 の等辺 N 角度 (たとえば、N = 5 の正五角形) です。「ターゲット」としての各カタツムリは、他のカタツムリに到達するように設定されています-隣接する頂点に立っていたもの（隣接するノード選択の方向が常に同じであるという事実、つまり、各カタツムリはただ「追いかける」だけです1 本のねじで、それぞれのカタツムリはちょうど 1 匹のカタツムリに「追われ」ます - カタツムリが行う選択は最初に 1 回だけで、追跡が終わるまで変化しません)。ある瞬間、カタツムリは目標に向かって動き始めます（いつでも目標に向かって正確に一直線に進みます）。すべてのカタツムリが一点で互いに接触しなくなるまで続きます。この状況をよりよく説明するために、次の図を見てください。

図解解説

矢印は、選択されたターゲット、それぞれのカタツムリがどのように表示されるかを示しています。十字は、すべてが互いに接触するおおよその位置を示します。あなたの仕事は、それぞれのカタツムリが来る距離を決定することです (すべてのカタツムリはまったく同じ距離になります)。結果が小数点以下 2 桁を超える場合は、小数点以下 2 桁を四捨五入します。

要約すれば：

入力

テスト数 T

N の次の T 行

出力

各テストについて、追跡中に各カタツムリが来る距離 (結果は小数点以下第 2 位に丸められます)。

サンプル入力:

5

3

5

7

9

91

出力：

0.67

1.45

2.66

4.27

419.69

そして、サンプル入力から目的の出力を取得する方法を誰かが説明し、使用できるアルゴリズムを提案してくれることを願っています。

お時間をいただきありがとうございます

4

2 に答える 2

2

ここでは物理が必要です。アリの 1 つの参照フレームからそれを見てください。そのため、常に 1 匹のアリがそこに向かって移動しています。次に、アリを結ぶ線に沿って相対速度をとります。これは v(1-cos(2*pi)/N) になります (これを解決してください。簡単です)

変位がエッジ長に等しい場合に、それらが出会うようになりました。したがって、所要時間は 1/v(1-cos((2*pi)/n)) です。移動距離は v*t なので、距離は 1/(1-cos((2*pi)/N)) です。

ここで直接式を確認できます。

http://mathworld.wolfram.com/MiceProblem.html

于 2012-05-28T14:35:58.887 に答える
1

次のように見ることもできます: カタツムリは正多角形の頂点から始まるため、すべて同じ速度でターゲットに向かってまっすぐに移動するため、常に正多角形の頂点にとどまります。したがって、中心からカタツムリへの光線とカタツムリの運動方向との間の角度は一定です。つまり、カタツムリの経路は対数螺旋です。

と 0z(t) = e^{ct}の間の対数螺旋の部分の長さは です。|z| = 1|c|/|Re c|

与えられた状況でc = e^{2π i/N} - 1 = (cos(2π/N) - 1) + i*sin(2π/N)は、 (スケーリングまで) はスパイラルのパラメーターです。

さて|c| = 2*sin(π/N)と|Re c| = 1 - cos(2π/N) = 2*sin²(π/N)ですから、始点と合流点の間の距離が 1 の場合、それぞれのカタツムリは 移動します1/sin(π/N)。ただし、ポリゴンの辺が 1 であり、中心と頂点の間の距離ではないという条件があったため、スケーリングする必要があります。便利なことに、中心と頂点の間の距離が 1 の場合、辺の長さは です|c|。したがって、移動距離の式は辺1/|Re c| = 1/(1 - cos(2π/N)の長さ のように簡略化され1ます。(1)

(¹) もちろん、これは @sukun007 が得た結果とまったく同じですが、異なる方法で導き出されただけです。

于 2012-05-28T15:09:51.047 に答える