2016年7月31日 星期日

Codeforces 594B. Max and Bike (數學題)

/*
    題目連結

    蠻數學的一題 
    難得我解的出來就發個題解吧~

    看完題目 我們就會很想列個關係式
    可是起終點 sensor 的位置 彼此相關
    但關係又不是很明確的 使我們很頭大

    不過既然我們要的是最佳解 那我們就不一定
    得列出 一般情形下 sensor 起終點的關係式
    而可以先觀察一下 最佳解有沒有什麼性質
    來替我們化簡情況

    令輪子實際跑的距離為L
    會發現 我們的 sensor 繞了 L/R = theta度
    而我們"省"的距離 (f-s-L) 就是夾theta度的
    起始邊和終邊 投影到 x軸的距離
    不難發現 讓sensor在起終點時 
    有相同的高度 是最佳解的必要條件

    依據此列式 我們有
    2R*abs(sin(theta/2) )+R*theta == f-s
    整理一下 =>
    2R*(theta/2+abs(sin(theta/2) ) ) == f-s
    有著 x+abs(sin(x) ) == c 的形式
    這是個遞增函數 我們用二分搜可以得到x
    最後再以 L = R*theta, t = L/v 便能得到答案
*/
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int n, R, v;

int main()
{
    scanf("%d %d %d", &n, &R, &v);

    for (int ni = 0; ni < n; ni++)
    {
        int s, f;
        scanf("%d %d", &s, &f);

        double y = (f-s)/2.0/R;

        double l = 0, r = y+1;
        for (int i = 0; i < 60; i++)
        {
            double mid = (l+r)/2;

            if ( mid+abs(sin(mid) ) < y ) l = mid;
            else r = mid;
        }

        printf("%.9f\n", l*2*R/v);
    }
}

沒有留言:

張貼留言