传送门
首先,将组成山的线段延长,形成许多直线,发现要使得这座山的任何一个部位都能够被看到,灯必须在所有直线之上,假设灯的坐标为(x,y),这可以转化为所有直线上横坐标与之相同的一点(x,y0),有y0≤y,根据贪心的原则,我们根据x算出所有y0后,取一个最大值就可以得出y。
设根据x算出的纵坐标y满足y=f(x),我们发现f(x)是一个下凸函数,于是三分即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| #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)); }
|