半平面交。
半平面指的就是一条直线的左面(也不知道对不对)
半平面交就是指很多半平面的公共部分。
这道题的解一定在各条直线的半平面交中。
而且瞭望塔只可能在各个点或者半平面交折线的拐点处。
求出半平面交,枚举即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-7
using namespace std;
const int maxn = 300 + 10; struct Point {
double x,y;
}p[maxn],t; struct Line {
double k,b; void init(Point p1,Point p2) {
k=(p1.y-p2.y)/(p1.x-p2.x);
b=p2.y-k*p2.x;
}
}l[maxn],s[maxn]; int n,sp;
double res=1e11; bool cmp(Line x,Line y) {
if(abs(x.k-y.k)<eps) return x.b<y.b;
return x.k<y.k;
} Point inter(Line l1,Line l2) {
Point res;
res.x=(l2.b-l1.b)/(l1.k-l2.k);
res.y=l1.k*res.x+l1.b;
return res;
} void push(Line l) {
while(sp>=2 && inter(s[sp],l).x < inter(s[sp-1],s[sp]).x) sp--;
s[++sp]=l;
} double f(double x) {
double res=0;
for(int i=1;i<=sp;i++) res=max(res,s[i].k*x+s[i].b);
return res;
} double g(double x) {
int i;
for(i=n;i&&x<p[i].x;i--);
return p[i].y+(x-p[i].x)/(p[i+1].x-p[i].x)*(p[i+1].y-p[i].y);
} int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lf",&p[i].x);
for(int i=1;i<=n;i++) scanf("%lf",&p[i].y);
for(int i=1;i<n;i++) l[i].init(p[i],p[i+1]);
sort(l+1,l+n,cmp);
for(int i=1;i<n;i++) if(i==n-1 || abs(l[i].k-l[i+1].k)>eps) push(l[i]); for(int i=1;i<=n;i++) res=min(res,f(p[i].x)-p[i].y);
for(int i=1;i<sp;i++) {
t=inter(s[i],s[i+1]);
res=min(res,t.y-g(t.x));
}
printf("%.3lf\n",res);
return 0;
}