mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #330 (Div. 1) B. Max and Bike

CodeForces

問題

解法

問題の様にセンサを取り付けると, センサはサイクロイドと呼ばれる軌道を描きます。
d = f-s とすると, d の $2\pi r$ の部分の倍数の部分はどうなろうと関係ないので, 結局のところ調べるべき図形は以下のような部分だけになります。

f:id:mayokoex:20151109190922j:plain

$\theta$ は左右で等しくなるのが最適でしょう。
これらの情報が与えられた時, $\theta$ をどう求めるかを考えます。

図を見るとわかるように, $2r(\theta-\sin(\theta)) = 2\pi r - d$ です。 $2\pi r - d$ は計算できるので, この値になるように $\theta$ を調整したいですが, $r(\theta - \sin(\theta))$ が単調増加関数であることを用いると, これは二分探索で求めることが出来ます。このようにして $\theta$ を求めます。すると, この区間の中で実際に走る距離は $2\pi r - 2r\theta$ となります。

得た知見

問題の本質とは関係ないけど long double の出力を printf("%.10Lf\n", ans); ってやると変な数字が出るらしい
- 手元では普通に出力されるんだけどこどふぉではダメ
- なので double に戻してから printf を使うのが良さ気(long double で出力できる方法があったら教えて欲しいです)

typedef long long ll;
typedef long double Real;

const Real PI = acos(-1.0);

int n, r, v;

inline Real calc(Real theta) {
    return r*(theta-sin(theta));
}

int main() {
    cin >> n >> r >> v;
    while (n--) {
        int s, f;
        scanf("%d%d", &s, &f);
        Real d = f-s;
        ll ni = d/(2*PI*r);
        Real D = (1+ni)*(2*PI*r) - d;
        if (D > 2*PI*r) D -= 2*PI*r;
        Real low = 0, high = PI;
        for (int i = 0; i < 60; i++) {
            Real med = (high+low) / 2;
            if (2*calc(med) > D) high = med;
            else low = med;
        }
        Real theta = (low+high)/2;
        d -= 2*r*sin(theta);
        double ans = d/v;
        printf("%.10lf\n", ans);
    }
    return 0;
}