京都大学プログラミングコンテスト2015 E - マッサージチェア2015
嘘解法っぽいけど通ってしまった。正当性あるんですかね。
解法
H > W と仮定します。
とりあえず, 三角形の一つの頂点は長方形の頂点と一致し, 残りの頂点は長方形の辺と重なるようにあるはずです。
ということで, 以下のような感じで a, b をとります。
すると, 三角形の辺の二乗の候補は 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; }