## Problem
哈姆噴射機 (Hamjet) 是飛機工程領域真正的奇蹟，它裝載了一個功率非常強大的發動機，在起飛時會立即燃燒掉所有燃料。而且它還沒有機翼，畢竟當機身是由特殊的菁錡 (Wonderflonium) 同位素製成而使其免疫任何傷害時，誰還需要機翼呢？

駕駛哈姆機並不是理想中性格溫順的超級英雄的工作。這就是為什麼哈姆機是屬於哈默機長 (Captain Hammer) 的，因為他本人和哈姆機一樣無堅不摧。據他所言，他每次在駕駛哈姆機飛行時總會感受到「傳=奇」般的加速度。

哈姆機以 $\theta$ 度 (單位：角度) 向上和每秒 **V** 公尺的速度起飛。**V** 是一個固定值，且由哈姆機發動機的功率和裝載的燃料多寡決定。目的地為距離 **D** 公尺的地面。你的工作是編寫哈姆機起飛角度控制的演算法，在給定 **V** 和 **D** 的條件下計算出起飛角度 $\theta$。

幸運的是，由菁錡所製成的哈姆機機體不受任何空氣阻力影響。更幸運的是，哈姆機不會飛的太高或太遠，因此你可以假設地球是平的，並且重力加速度恆為 $9.8$ $m/s^2$ 垂直地平面向下。
## Input
輸入的第一行有一個正整數 **T** 表示測資數量。緊接著會有 **T** 行。每行均代表一個測資並含有兩個正整數且依序為 **V** 和 **D**，中間以空白隔開。
## Output
對每筆測資，均印出一行格式為 `Case #x: θ` 的字串，而其中的 `x` 為測資編號 (從 1 開始)，$\theta$ 為自地平面向上的起飛角度。倘若有多個可能的答案，則輸出最小且非負的那個。

$\theta$ 須為一個 9 位小數 (若位數不足 9 位，則須補零至 9 位)，且有一個 $10^{-6}$ 的相對與絕對誤差容許範圍 (註 2.)。
## Limits
時間限制：60 秒。
記憶體限制：1 GB。
$1 \le$ **T** $\le 4500$；
$1 \le$ **V** $\le 300$；
$1 \le$ **D** $\le 10000$；
保證所有測資一定有解。
## Sample
#### Sample Input

3
98 980
98 490
299 1234

#### Sample Output

Case #1: 45.000000000
Case #2: 15.000000000
Case #3: 3.887092786

---

第一筆測資飛行示意圖：


第二筆測資飛行示意圖：


第三筆測資飛行示意圖：


## Datasets
* [Input Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/captain_hammer/data/secret/subtask1/1.in)
* [Output Raw](https://github.com/google/coding-competitions-archive/raw/main/kickstart/2013/practice_round/captain_hammer/data/secret/subtask1/1.ans)
## Solution
:::spoiler Editorial (C++11)

---

### Algorithm
本題的題目要求很簡單，給定距離 **D** 與速率 **V**，求起飛角度 $\theta$。本題只要對斜向拋射運動有一定的理解，便可以透過物理計算得出答案。考慮以下的斜向拋射運動：
初速度 $V$ 可以被拆解為水平與垂直方向的分速度 $V_h$ 和 $V_v$，且顯然會有：
> $V_h = V \cos \theta$
> $V_v = V \sin \theta$

而其中垂直方向的速度 $V_v$ 則是影響飛行時間 (即滯空時間) 的主要因素。拋體 (即 Hamjet) 在垂直方向上會不斷減速，直至不再上升 (速度為 0)，且滿足：
> $t_{max} = {V_v \over g}$

其中 $t_{max}$ 為從出發至最高點所需時間，$g$ 為重力加速度 $9.8$ $m/s^2$。

而因為地板是水平的，因此拋體運動的軌跡應為一左右對稱之拋物線，故左右兩半的歷時應相等，因此有：
> $t_{total} = 2 \times t_{max}$

其中 $t_{total}$ 表總歷時。

如此一來，我們便能夠得知其水平運動距離應為水平運動速率乘上總歷時：
> $D = V_h \times t_{total}$

其中 $D$ 表目的地距離。

將所有等式代入得到：
> $D = (V \cos \theta) \times (2 \times {V \sin \theta \over g})$

化簡並移項得到：
> $2 \sin \theta \cos \theta = {Dg \over V^2}$

利用正弦兩倍角公式化簡得到：
> $\sin {2 \theta} = {Dg \over V^2}$

兩邊同時取反正弦函式：
> $2 \theta = \{\sin^{-1} {Dg \over V^2},\pi - \sin^{-1} {Dg \over V^2}\} + 2 \pi k ; k \in \mathbb{Z}$

要注意到由於正弦函式的特性使得互補角的正弦值相同，因此取反正弦函式後會有兩個不同界角以及其同界角。然而，對於答案 $\theta$ 有以下範圍：
> $0 < \theta < {\pi \over 2}$
> $0 < 2 \theta < \pi$

若超出此範圍則顯然不合理。而又要求輸出較小的角度，且當 $x \ge 0$ 時以下不等式恆成立：
> $0 \le \sin^{-1} x \le \pi - \sin^{-1} x$

因此答案應為：
> $\theta = {1 \over 2} \sin^{-1} {Dg \over V^2}$
### Implementation
#### Step 1: 編寫基本框架
為了使用 C++ 的標準函式庫，需要引入 `stdc++.h` 標頭檔：

#include <bits/stdc++.h>

為了更加快速的使用 `std` 命名空間，加入以下程式：

using namespace std;

接著定義 `main` 函式內容：

int main() {}

於 `main` 函式中加入輸入輸出優化：

ios::sync_with_stdio(false);
cin.tie(nullptr);

因題目要求要輸出 9 位小數，因此須設定浮點數精確度：

cout << fixed << setprecision(9);

##### Step 1 程式

#include <bits/stdc++.h>

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(9);
}

#### Step 2: 處理輸入資料
讀取輸入之測資數量 **T** 於 `case_cnt`：

int case_cnt;
cin >> case_cnt;

對每筆測資，讀取輸入之速率 **V** 和距離 **D** 分別於 `vel`、`dis`：

int vel, dis;

for (int i = 0; i < case_cnt; ++i) {
    cin >> vel >> dis;
}

至此便完成了對輸入資料的處理，接著就可以開始編寫演算法。
##### Step 2 程式

#include <bits/stdc++.h>

using namespace std;


int vel, dis;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(9);
    int case_cnt;
    cin >> case_cnt;
    for (int i = 0; i < case_cnt; ++i) {
        cin >> vel >> dis;
    }
}

#### Step 3: 編寫演算法
創建一函式 `solve` 回傳一浮點數作為答案：

double solve() {}

於 `main` 函式中輸出答案：

cout << "Case #" << i + 1 << ": " << solve() << '\n';

接著於 `solve` 函式內實作公式：
> $\theta = {1 \over 2} \sin^{-1} {Dg \over V^2}$

由於浮點數運算過程中會有誤差累積，因此為了提高答案的精確度，要優先處理可能的整數乘法，並盡可能的減少浮點數的轉換與運算。
而其中的重力加速度 $g = 9.8$ 亦可被拆為兩個整數相除 ($98 \over 10$)，增加整數運算。

重新整理過後的公式為：
> $\theta = 0.5 \sin^{-1} {98D \over 10V^2}$

題目要求的輸出單位為角度，但 C++ 的標準 `asin` 函式的輸出單位為弧度，因此須再做一次單位轉換：
> ${\theta}^{\circ} = {180^{\circ} \over \pi} \times 0.5 \sin^{-1} {98D \over 10V^2} = {90^{\circ} \over \pi} \sin^{-1} {98D \over 10V^2}$

接著便進入實作環節，定義重力加速度 $g$ 的分子分母：

#define G_ACCEL_NUM 98
#define G_ACCEL_DEN 10

先計算反三角函式內的分數之分子部分 $98D$：

double num = G_ACCEL_NUM * dis;

再計算反三角函式內的分數之分母部分 $10V^2$：

double den = vel * vel * G_ACCEL_DEN;

此時要加一個防溢出機制，避免極端狀況時因浮點數誤差導致 `num / den` 些微大於 1，此時會造成對 `asin` 函式的範圍溢出，產生錯誤的結果。若 `num / den` 之值大於 1，則直接輸出其等於 1 時之極端狀況，即 ${90^{\circ} \over \pi} \sin^{-1} 1 = 45^{\circ}$：

if (num >= den)
    return 45.0;

否則照常輸出即可：

return asin(num / den) / M_PI * 90.0;

##### solve 函式內容

double solve() {
    double num = G_ACCEL_NUM * dis;
    double den = vel * vel * G_ACCEL_DEN;
    if (num >= den)
        return 45.0;
    return asin(num / den) / M_PI * 90.0;
}

#### Full Code

#define G_ACCEL_NUM 98
#define G_ACCEL_DEN 10

#include <bits/stdc++.h>

using namespace std;


int vel, dis;

double solve() {
    double num = G_ACCEL_NUM * dis;
    double den = vel * vel * G_ACCEL_DEN;
    if (num >= den)
        return 45.0;
    return asin(num / den) / M_PI * 90.0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(9);
    int case_cnt;
    cin >> case_cnt;
    for (int i = 0; i < case_cnt; ++i) {
        cin >> vel >> dis;
        cout << "Case #" << i + 1 << ": " << solve() << '\n';
    }
}

### Complexity Analysis
#### 總時間複雜度：$O(T)$
* `Line 25-28`：$t(T) = O(T)$，因從 `0` 開始遍歷至 `case_cnt - 1`。

總時間複雜度：$t(T, V, D) = O(T)$
#### 額外時間複雜度：$O(1)$
額外時間複雜度表演算法在對整理後的輸入資料進行計算所需的時間複雜度，而本題只需要代公式便可直接得出答案，故額外時間複雜度為 $O(1)$
#### 總空間複雜度：$O(1)$
#### 額外空間複雜度：$O(1)$
:::
## Notes
1. 題目的背景設定來源於 2008 年的一部音樂迷你劇《糟糕博士的歡唱部落格》(Dr. Horrible's Sing-Along Blog)，此音樂劇在當時獲得了很大的反響，也榮獲了多項獎項，如最佳網絡劇觀眾選擇獎、最佳喜劇網絡劇導演獎、最佳喜劇網絡劇編劇獎、最佳喜劇網絡劇男演員 (哈里斯) 獎、最佳剪輯、最佳攝影和最佳原創音樂獎。
2. 即只要相對誤差或絕對誤差任一者小於 $10^{-6}$ 即可。舉例而言，若標準答案為 `1234567.890000000`，那麼容許的絕對誤差範圍為 $1234567.89 \pm 10^{-6}$，即 $[1234567.889999000, 1234567.890001000]$；容許的相對誤差範圍為 $1234567.89 \pm 10^{-6} \times 1234567.89$，即 $[1234566.655432110, 1234569.124567890]$。由於只要有任一範圍達到即可，因此最終的容許範圍應為兩誤差範圍的聯集，即後者；同上所述，若標準答案為 `0.123456789`，那麼修正過後的絕對誤差範圍為 $[0.123455789, 0.123457789]$，相對誤差範圍為 $[0.123456666, 0.123456912]$，取聯集即為前者。
## References
1. https://github.com/google/coding-competitions-archive/blob/main/kickstart/2013/practice_round/captain_hammer/statement.pdf
2. https://en.wikipedia.org/wiki/Dr._Horrible%27s_Sing-Along_Blog