UVa10773 - Back to Intermediate Math (數論 Math theorm)

題目大意

給你河流寬度 d、河流速度 v、船速 u，想詢問一個小學生都可以回答的問題，船要渡河，我們想請問兩種方式相差的秒數為多少？

如果算不出來或這兩條路徑相同請輸出 can’t determine

• 最短路徑
  也就是直線經過
• 最快速度
  順著河流速度經過

分析

這題不是難題，但也不太像是水題，因為他需要用到三角函數與反三角函數。我都沒學好於是去 wiki 查詢了一陣子QQQ。

算出最短路徑所花費的秒數再算出最快速度所花費的秒數之後相減即可。

值得注意的是算最短路徑比較麻煩，且有一些例外案例。

重點觀念

• 兩個路徑的長度必須是 double
• 秒數沒有正負，因此要加絕對值
• 判斷是否輸出 can’t determine
  • 船速等於 0，則永遠不會到終點
  • 河流流速等於 0，則兩條路徑相同，題目 output 有說明一定要這兩條路徑不同才可以輸出答案
  • 如果河流速度大於船的速度，則最短路徑則沒辦法抵達終點
• 不可以判斷 d = 0 則不可以輸出 can’t determine
  題目的坑…，他有可能 d 是 0，那這兩條路徑則視為不相同，但我覺得理應相同，不過是題目 bug 就算了www。
• 最短路徑與最快速度，先給出圖

  

  • 最快路徑公式(Shortest Time) \(d / u \)
    • 因為是最快路徑，因此我們順著河流，藉此讓船速跟河流速度的抵抗將至 0。所以只要距離除以船速即可。
  • 最短路徑公式(Shortest Path) \( cosθ = cos(arcsin(v / u))\)，前面是 v，後面是 u
    • 根據上面的圖我們可以知道河流會影響到我們的行進速度，於是我們需要更多時間來保證我們行徑的是最短路徑，因此船速要去抵抗河流速度，因此當河流往右時則我們船方向就往左來走出最短路徑。

    • 
      根據上圖可以看到類似於最短路徑的三角形產生， v 就是 x 然後 u 就是 1，因此 \(v / u \)就是我們需要的 \(cos(arcsin(v / u))\)，但要注意的是還需要乘以 u，因為我們剛剛是透過三角形公式先轉換成符合套件的度量衡，現在再乘回來才會得到正確答案

    • 之後與最快路徑公式相同，讓 \(d / (u * cos(arcsin(v / u))) \) 即可。

參考來源

• 齊笎詳解
• 反三角函數 - wiki

心得

這個好難QQQ，竟然要用到三角函數，快把我給考倒了拉！！幸好有隊友的詳解來讓我快速學會，不然我在學習這題目的過程中一定會卡很久的關XD。

如果比賽要用到三角函數，我可能要先投降了..。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int kase ;
double n , u , d , v ;
double fast ,shortest ;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    cin >> n ;
    while(n--){
        cin >> d >> v >> u;
        cout << "Case " << ++kase << ": " ;
        if(u == 0 || v == 0 || v >= u ){
            cout << "can't determine" << '\n' ;
            continue ;
        }

        fast = 0 ; shortest = 0 ;
        fast = d / u ;
        shortest = d / (u *cos(asin(v/u)));
        //cout << fast << ' ' << shortest << '\n' ;
        cout << fixed << setprecision(3) << abs(fast - shortest ) << '\n' ;
    }
    return 0;
}