自动搬运

查看原文

来自洛谷，原作者为

	W_C_B_H 可互关，要求：我和你很熟或你至少是绿名（棕名的会暂时取关，建议棕名结束后私信我）| 右键红框后点检查，找到其下一个 div 的 style 中的 display: none;，将其删掉即可看主页 | 风井省最菜 8.5 年级 OIer

搬运于2025-08-24 23:14:06，当前版本为作者最后更新于2025-04-20 19:27:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设一次函数 $f_i(x)=p_ix+q_i$ 经过点 $(-10^5,a_i)$ 和 $(10^5,b_i)$，则有：

$$\begin{cases}-10^5\times p_i+q_i=a_i\\10^5\times p_i+q_i=b_i\end{cases} $$

解得：

$$\begin{cases}p_i=\dfrac{b_i-a_i}{2\times10^5}\\q_i=\dfrac{a_i+b_i}{2}\end{cases} $$

设 $\begin{aligned}f(x)=\max_{1\le i\le n}f_i(x)\end{aligned}$，则答案即为 $-10^5\le x\le 10^5$ 时，$f(x)$ 的最小值。

观察可得，$f(x)$ 有且仅有这三种情况：

• 在 $[-10^5,10^5]$ 上单调不降。

• 在 $[-10^5,10^5]$ 上单调不增。

• 存在 $-10^5 < x < 10^5$，使得 $f(x)$ 在 $[-10^5,x]$ 上单调不增，在 $[x,10^5]$ 上单调不降。

所以我们可以用三分算法求出 $f(x)$ 的最小值。

Code：

import java.util.Scanner;
public class Main {
    static final int N = 100005;
    static final double eps = 1e-3;
    static int n;
    static double[] p = new double[N], q = new double[N];
    static double f(double x) {
        double ret = 0d;
        for(int i = 1; i <= n; i++) {
            ret = Math.max(ret, p[i] * x + q[i]);
        }
        return ret;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        for(int i = 1; i <= n; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            p[i] = (b - a) / 2e5;
            q[i] = (a + b) * 0.5;
        }
        double l = -1e5, r = 1e5, mid1, mid2;
        while(r - l > eps) {
            mid1 = l + (r - l) / 3;
            mid2 = r - (r - l) / 3;
            double f1 = f(mid1), f2 = f(mid2);
            if(f1 < f2) {
                r = mid2;
            } else {
                l = mid1;
            }
        }
        System.out.printf("%.2f", f(l));
        sc.close();
    }
}