这题做的真是。。心力交瘁。。其实就是一个半平面交，然而我发现自己实际上完全不会这个东西。
据说模拟退火和三分都可以做，但是考虑将每条边的上半部分求交，最后这个凸包上的点和原折线的这点才可能是答案。
证明应该是分段一次函数的极致只可能出现在端点上。
剩下的就是一系列半平面交模板的问题了，写了一个先将两点式转成点斜式直线方程再求交的函数，WA，发现点斜式根本不能处理与y轴平行的直线。
然后又看了以前模板中的定比分点叉积求交的函数，WA，发现这个只能求线段交点。
https://blog.csdn.net/u013050857/article/details/40923789
最后极不情愿地写了将式子化到底的做法，感觉这个函数根本背不下来。
不过幸好发现了这个问题，否则考场上要是写了就会很惨。
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef double db;
using namespace std; const int N=;
const double eps=1e-;
int n,tot,cnt;
db ans=1e60;
struct P{ db x,y; }p[N],a[N];
struct L{ P a,b; db sl; }l[N],q[N],tmp[N]; double dmult(P a,P b,P c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); }
bool operator <(const L &a,const L &b){ return (a.sl!=b.sl) ? a.sl<b.sl : dmult(a.a,a.b,b.b)<-eps; } P inter(L a,L b){
double A1=a.b.y-a.a.y,B1=a.a.x-a.b.x,C1=-B1*a.a.y-A1*a.a.x;
double A2=b.b.y-b.a.y,B2=b.a.x-b.b.x,C2=-B2*b.a.y-A2*b.a.x;
return (P){(C1*B2-C2*B1)/(B1*A2-B2*A1),(C1*A2-C2*A1)/(A1*B2-A2*B1)};
}
bool jud(L a,L b,L c){ P t=inter(a,b); return dmult(c.a,c.b,t)<-eps; } void work(){
tmp[++tot]=l[];
rep(i,,cnt) if (fabs(l[i].sl-l[i-].sl)>eps) tmp[++tot]=l[i];
rep(i,,tot) l[i]=tmp[i];
int L=,R=; q[++R]=l[]; q[++R]=l[];
rep(i,,tot){
while (L<R && jud(q[R-],q[R],l[i])) R--;
while (L<R && jud(q[L+],q[L],l[i])) L++;
q[++R]=l[i];
}
while (L<R && jud(q[R-],q[R],q[L])) R--;
while (L<R && jud(q[L+],q[L],q[R])) L++;
tot=; rep(i,L,R-) p[++tot]=inter(q[i],q[i+]);
} void getans(){
rep(k,,tot)
rep(i,,n-){
P t=(P){p[k].x,-};
if (p[k].x>=a[i].x && p[k].x<=a[i+].x)
ans=min(ans,p[k].y-inter((L){a[i],a[i+]},(L){t,p[k]}).y);
}
rep(k,,n)
rep(i,,tot-){
P t=(P){a[k].x,-};
if (a[k].x>=p[i].x && a[k].x<=p[i+].x)
ans=min(ans,inter((L){p[i],p[i+]},(L){t,a[k]}).y-a[k].y);
}
} int main(){
scanf("%d",&n);
rep(i,,n) scanf("%lf",&a[i].x);
rep(i,,n) scanf("%lf",&a[i].y);
a[]=(P){a[].x,}; a[n+]=(P){a[n].x,};
rep(i,,n) l[++cnt]=(L){a[i],a[i+],atan2(a[i+].y-a[i].y,a[i+].x-a[i].x)};
sort(l+,l+cnt+); work(); getans(); printf("%.3lf\n",ans);
return ;
}
UPD:感觉自己十分愚蠢，与y轴平行的直线判一下不就好了。
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
#define A double k2=(b.b.y-b.a.y)/(b.b.x-b.a.x),b2=b.a.y-k2*b.a.x
#define B double k1=(a.b.y-a.a.y)/(a.b.x-a.a.x),b1=a.a.y-k1*a.a.x
typedef double db;
using namespace std; const int N=;
const double eps=1e-;
int n,tot,cnt;
db ans=1e60;
struct P{ db x,y; }p[N],a[N];
struct L{ P a,b; db sl; }l[N],q[N],tmp[N]; double dmult(P a,P b,P c){ return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y); }
bool operator <(const L &a,const L &b){ return (a.sl!=b.sl) ? a.sl<b.sl : dmult(a.a,a.b,b.b)<-eps; } P inter(L a,L b){
if (a.a.x==a.b.x){ A; return (P){a.a.x,k2*a.a.x+b2}; }
if (b.a.x==b.b.x){ B; return (P){b.a.x,k1*b.a.x+b1}; }
A; B; double x=(b2-b1)/(k1-k2),y=k1*x+b1;
return (P){x,y};
} bool jud(L a,L b,L c){ P t=inter(a,b); return dmult(c.a,c.b,t)<-eps; } void work(){
tmp[++tot]=l[];
rep(i,,cnt) if (fabs(l[i].sl-l[i-].sl)>eps) tmp[++tot]=l[i];
rep(i,,tot) l[i]=tmp[i];
int L=,R=; q[++R]=l[]; q[++R]=l[];
rep(i,,tot){
while (L<R && jud(q[R-],q[R],l[i])) R--;
while (L<R && jud(q[L+],q[L],l[i])) L++;
q[++R]=l[i];
}
while (L<R && jud(q[R-],q[R],q[L])) R--;
while (L<R && jud(q[L+],q[L],q[R])) L++;
tot=; rep(i,L,R-) p[++tot]=inter(q[i],q[i+]);
} void getans(){
rep(k,,tot)
rep(i,,n-){
P t=(P){p[k].x,-};
if (p[k].x>=a[i].x && p[k].x<=a[i+].x)
ans=min(ans,p[k].y-inter((L){a[i],a[i+]},(L){t,p[k]}).y);
}
rep(k,,n)
rep(i,,tot-){
P t=(P){a[k].x,-};
if (a[k].x>=p[i].x && a[k].x<=p[i+].x)
ans=min(ans,inter((L){p[i],p[i+]},(L){t,a[k]}).y-a[k].y);
}
} int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%lf",&a[i].x);
rep(i,,n) scanf("%lf",&a[i].y);
a[]=(P){a[].x,}; a[n+]=(P){a[n].x,};
rep(i,,n) l[++cnt]=(L){a[i],a[i+],atan2(a[i+].y-a[i].y,a[i+].x-a[i].x)};
sort(l+,l+cnt+); work(); getans(); printf("%.3lf\n",ans);
return ;
}