Steven_MengのBlog

传送门

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

 评论