尋找適當的算法

Question

我有一個問題，從SPOJ類似平臺解決，我不能想出如何解決這個問題。這裏是這個問題，用G翻譯器翻譯，但如果有東西丟失，我可以嘗試更好地翻譯它

該條目給出了測試次數T（10 < = T < = 100）。對於每個測試，給出數字N（3 < = N < = 100）。這個數字是等邊N角（例如，等邊五邊形，N = 5），邊爲1.在N-gon的N個頂點的每一個上都播種了蝸牛。作爲「目標」的每個蝸牛已經設置了一隻蝸牛到達另一隻蝸牛 - 站在相鄰頂點上的蝸牛（事實上，相鄰節點選擇的方向始終相同，即，每隻蝸牛「追逐」只是一顆螺絲釘和每隻蝸牛都被一隻蝸牛「追趕」 - 蝸牛一開始只能選擇一次，直到追逐結束纔會改變）。有一段時間，蝸牛開始向其目標邁進（隨時與其目標完全一致）。它一直持續到所有的蝸牛都不會在一點上相互接觸。爲了更好地說明這種情況，請看看下面的圖片：

Illustrated explanation

箭頭顯示的是如何選擇的目標，每個蝸牛。十字表示所有接觸對象的大致位置。你的任務是確定每頭蝸牛的距離（所有距離都會完全相同）。如果結果是小數點後兩位以上是小數點後第二位。

總結：

輸入

測試的T數量

在N

下一Ť線

輸出

對於每個測試，該距離在追逐期間來到每頭蝸牛（結果）四捨五入到小數點後兩位）。

樣品輸入：

輸出：

0.67

1.45

2.66

4.27

419。69

我的願望是有人向我解釋如何從樣本輸入中獲得所需的輸出，並可能提出一些我可以使用的算法。

感謝您的時間提前

Answer 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

Answer 2

您也可以看看這樣說：蝸牛在正多邊形的頂點開始，這樣以來他們都移動以相同的速度和直朝着自己的目標，他們將始終保持在頂點的正多邊形。因此，從中心到蝸牛的射線與蝸牛的運動方向之間的角度是恆定的。這意味着蝸牛的路徑是Logarithmic spirals。

|z| = 1與0之間的對數螺線z(t) = e^{ct}部分的長度爲|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具有相同的結果，只是導出方式不同而已。