Codeforces 549H: 退化矩陣 - 二分查找求最小範數

其中 ε 即為我們要最小化的範數。矩陣 B 退化等價於 xw - yz = 0，即 xw = yz。

對於固定的 ε，xw 的取值範圍為 [min₁, max₁]，yz 的取值範圍為 [min₂, max₂]。若這兩個區間有交集，則存在滿足條件的 B，說明該 ε 可行。利用這一單調性，可對 ε 進行二分查找。

區間乘積的極值計算

給定兩個區間 [L, R] 和 [l, r]，其乘積的最小值與最大值分別為：

min = min(L*l, L*r, R*l, R*r)
max = max(L*l, L*r, R*l, R*r)

只需計算四個端點乘積的極值即可。

算法流程

1. 初始化二分邊界：low = 0, high = 1e11（足夠大）。
2. 重複 170 次（足夠精度）：
   • mid = (low + high) / 2
   • 計算四個元素在 ±mid 擾動下的取值區間。
   • 求出 xw 和 yz 的值域區間。
   • 若兩區間相交，high = mid；否則 low = mid。
3. 輸出 high，保留 12 位小數。

樣例解析

輸入： 1 2 / 3 4
輸出： 0.2000000000
解釋： 最優 B 為 [[1.2, 1.8], [2.8, 3.2]]，行列式為 0，最大偏差 0.2。

複雜度分析

二分次數固定（170），每次檢查 O(1)，總時間 O(1)，空間 O(1)。極易實現且精度穩健。

參考代碼

import java.util.*;
public class Main {
    double a,b,c,d;
    double[][] range = new double[4][2];
    double getMin(double L,double R,double l,double r) {
        return Math.min(L*l, Math.min(L*r, Math.min(R*l, R*r)));
    }
    double getMax(double L,double R,double l,double r) {
        return Math.max(L*l, Math.max(L*r, Math.max(R*l, R*r)));
    }
    boolean check(double e) {
        range[0][0]=a-e; range[0][1]=a+e;
        range[1][0]=b-e; range[1][1]=b+e;
        range[2][0]=c-e; range[2][1]=c+e;
        range[3][0]=d-e; range[3][1]=d+e;
        double A=getMin(range[0][0],range[0][1],range[3][0],range[3][1]);
        double B=getMax(range[0][0],range[0][1],range[3][0],range[3][1]);
        double C=getMin(range[1][0],range[1][1],range[2][0],range[2][1]);
        double D=getMax(range[1][0],range[1][1],range[2][0],range[2][1]);
        return (A>=C && A<=D) || (B>=C && B<=D) || (C>=A && C<=B) || (D>=A && D<=B);
    }
    double Search() {
        double low=0, high=1e11;
        for(int i=0;i<170;i++) {
            double mid=(low+high)/2;
            if(check(mid)) high=mid; else low=mid;
        }
        return high;
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        Main m=new Main();
        m.a=in.nextDouble(); m.b=in.nextDouble();
        m.c=in.nextDouble(); m.d=in.nextDouble();
        System.out.printf("%.12f\n", m.Search());
    }
}