题解 P1663 【山】
Delva
2018-10-18 07:59:52
题意很好懂,由于有x[i+1]>x[i]的保证,可以转化为找到一个最低点在所有直线上方。用$f_i(x)$表示点i和点i+1联立的直线,不难发现,所有直线的上方交集$ y>=f_i(x)$的边界$max$ { $f_i(x)$ }为一个下凸函数,我们要找的即是函数最低点。通过三分法求极值,便能得到最低点。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define LL long long
template<class T>inline void read(T &aa) {
int k=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar()) k=(k<<3)+(k<<1)+(c-'0');aa=k*f;
}
const int maxn = 5010;
const double eps = 1e-8;
struct P{P(){}double x,y;}A[maxn];
int n;
double getY(double x0){//获得横坐标为x0时放灯的最低点
double res = 0.0;
for(int i=1;i<n;++i){
res=max(res,A[i].y+(x0-A[i].x)*(A[i].y-A[i+1].y)/(A[i].x-A[i+1].x));//联立点i与点i+1得到下凸函数的值
}return res;
}
int main(void){
read(n);
for(int i=1;i!=n+1;++i)scanf("%lf%lf",&A[i].x,&A[i].y);
//三分法求极值(保证极值始终在l与r之间,通过比较m1和m2缩小范围)
double l=0.0,r=100000.0;
while(abs(l-r)>eps){
double m1 = (l+l+r)/3,m2 = (l+r+r)/3;
if(getY(m1)<getY(m2))r=m2;else l=m1;
}
printf("%.2lf",getY(l));
return 0;
}
```