P1663 山 [二分答案, 数学]

$山$

题目描述见链接, 请使用 $O(NlogN)$ 的复杂度解决这道题 .

---

$color{grey}{最初想法}$

首先发现答案一定是两条直线的交点 .

把所有直线按斜率从小到大排序, 然后得到一个类似上凸壳的东西, 尝试使用相邻直线的交点更新答案, 但是发现这样会出现交点在某条直线下方的情况 .

---

$color{red}{正解部分}$

考虑 二分答案, 二分出 $mid$ 表示最小高度, 然后去检查每条直线是否能够被照到,
对每条直线, 按斜率 $k$ 分类讨论,

• $k > 0$, 此时将 $mid$ 带进方程, 得到 $x$, 此时灯放在 $(-infin, x]$ 可以照亮该直线 .
• $k < 0$, 此时将 $mid$ 带进方程, 得到 $x$, 此时灯放在 $[x, infin)$ 可以照亮该直线 .
• $k = 0$, 此时若 $mid geq b$, 则可以照亮 .

遍历所有直线, 得到左边界 $L$ 和右边界 $R$, 若 $L le R$, 说明存在高度为 $mid$ 的灯满足条件 .

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 5005;
const double eps = 1e-12;

int N;

int X[maxn];
int Y[maxn];

bool chk(double mid){
        double L = 0, R = 100005;
        for(reg int i = 2; i <= N; i ++){
                double k = (1.0*Y[i]-Y[i-1])/(1.0*X[i]-X[i-1]);
                double b = 1.0*Y[i] - k*X[i];
                double x = (mid - b) / k;
                if(k > eps) R = std::min(R, x); 
                else if(k < -eps) L = std::max(L, x);
                else if(mid-b < eps) return false;
        }
        return R-L > eps;
}

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++) X[i] = read(), Y[i] = read();
        double l = 0, r = 1000005, Ans = r;
        while(r-l > eps){
                double mid = (l + r)/2;
                if(chk(mid)) Ans = std::min(Ans, mid), r = mid - 0.0001;
                else l = mid + 0.0001;
        }
        printf("%.2lf
", Ans);
        return 0;
}