Steven_Meng's Blog

传送门

首先，将组成山的线段延长，形成许多直线，发现要使得这座山的任何一个部位都能够被看到，灯必须在所有直线之上，假设灯的坐标为$(x,y)$，这可以转化为所有直线上横坐标与之相同的一点$(x,y_0)$，有$y_0 \le y$，根据贪心的原则，我们根据$x$算出所有$y_0$后，取一个最大值就可以得出$y$。

设根据$x$算出的纵坐标$y$满足$y=f(x)$，我们发现$f(x)$是一个下凸函数，于是三分即可。

#include <bits/stdc++.h>
#define eps 0.0001
#define MAXN 5005
using namespace std;
double k[MAXN];
int x[MAXN],y[MAXN];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int n;
inline double Calc(double m){
    double ans=0;
    for (register int i=1;i<n;++i){
        ans=max(ans,(double)y[i]+(m-(double)x[i])*k[i]);
    }
    return ans;
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i){
        x[i]=read(),y[i]=read();
    }
    for (register int i=1;i<n;++i){
        k[i]=(double)(y[i+1]-y[i])/(double)(x[i+1]-x[i]);
    }
    double l=0,r=1000000.0;
    while (l+eps<r){
        double mid1=(l*2.00+r)/3.00,mid2=(l+r*2.00)/3.00;
        if (Calc(mid1)<Calc(mid2)) r=mid2;
        else l=mid1;
    }
    printf("%.2lf\n",Calc(l));
}