mayoko’s diary

プロコンとかいろいろ。

京都大学プログラミングコンテスト2015 E - マッサージチェア2015

嘘解法っぽいけど通ってしまった。正当性あるんですかね。

解法

H > W と仮定します。

とりあえず, 三角形の一つの頂点は長方形の頂点と一致し, 残りの頂点は長方形の辺と重なるようにあるはずです。
ということで, 以下のような感じで a, b をとります。
f:id:mayokoex:20151025101724j:plain

すると, 三角形の辺の二乗の候補は H^2+a^2, W^2+b^2, (W-a)^2+(H-b)^2 になります。a を固定すると, W^2+b^2, (W-a)^2, (H-b)^2 を b についてこの 2 つの値の最小値を最大化することになりますが, これは明らかにこの2つの値が等しい時に最大になります(放物線がぶつかるところで最大になるでしょそれは)。
結果として, 2Hb = (W-a)^2 + (H^2-W^2) となるところで最大になるようです。

この後が適当なんですが, 評価関数として H^2+a^2 と 上で求めた b を使った W^2+b^2 の差の絶対値, を使うと a に関する凸関数になる気がします。ということで, a について 3 分探索すると通りました。

int H, W;
double calc(double a) {
    double b = ((W-a)*(W-a) + (H*H-W*W)) / (2*H);
    return abs(W*W+b*b - (H*H+a*a));
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> H >> W;
        if (H < W) swap(H, W);
        double low = 0, high = W;
        for (int i = 0; i < 100; i++) {
            double m1 = (low*2+high)/3, m2 = (low+high*2)/3;
            double r1 = calc(m1), r2 = calc(m2);
            if (r1 < r2) high = m2;
            else low = m1;
        }
        double a = (low+high)/2;
        double b  = ((W-a)*(W-a) + (H*H-W*W)) / (2*H);
        printf("%.10lf\n", sqrt(min({H*H+a*a, W*W+b*b, (H-b)*(H-b)+(W-a)*(W-a)})));
    }
    return 0;
}