KUPC2015 E マッサージチェア2015

2015/10/25 (Sun) AtCoder KUPC 三分探索

問題

日本語

方針

長方形の頂点を半時計回りに A, B, C, D とおく．A を使うことにすると，残りの 2 点は BC 上と CD 上にある． BC 上の方を仮定したとき，残りは線分上を動くので目的関数は下に凸な関数になる．なので三分探索ができる． BC 上の方も三分探索する．

実装

typedef long double ld;

ld H,W;

inline ld norm(ld a, ld b){
    return a*a + b*b;
}

ld h(ld x, ld y){
    ld res = 1e12;
    res = min(res, norm(x,y));
    res = min(res, norm(W-x, H));
    res = min(res, norm(H-y, W));
    return res;
}

ld g(ld x){
    ld l = 0, r = H;
    rep(i,70){
        ld m1 = (l+l+r) / 3, m2 = (l+r+r) / 3;
        ld h1 = h(x,m1), h2 = h(x,m2);
        if(h1 < h2) l = m1; else r = m2;
    }
    return h(x,l);
}

ld f(){
    ld l = 0, r = W;
    rep(i,70){
        ld m1 = (l+l+r) / 3, m2 = (l+r+r) / 3;
        ld g1 = g(m1), g2 = g(m2);
        if(g1 < g2) l = m1; else r = m2;
    }
    return sqrt(g(l));
}

int main(){
    int T;
    cin >> T;
    rep(i,T){
        cin >> H >> W;
        printf("%.10lf\n", (double)f());
    }
}