题解 P1663 【山】

Delva

2018-10-18 07:59:52

Solution

题意很好懂,由于有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; } ```