这回好好用半平面交写一次…

看了cls当年写的代码看了好久大概看懂了…cls太强辣

#include
#include
#include
#define rep(i,n) for(register int i=1;i<=n;i++) #define REP(i,a,b) for(register int i=a;i<=b;i++) #define debug(x) cout<<#x<<" = "<>1;
struct P
{
dl x,y;
P(dl x=0,dl y=0):x(x),y(y){}
}p[N],ps[N];
struct L
{
dl k,b;
}l[N];
inline bool operator < (L a,L b){return a.kb.b);}
inline bool operator==(L a,L b){return a.k==b.k;}
inline dl get_x(L a,L b){return -(b.b-a.b)/(b.k-a.k);}
inline dl get_val(L a,dl x){return a.k*x+a.b;}
inline L get_line(P a,P b)
{
L res;res.k=(a.y-b.y)/(a.x-b.x);
res.b=a.y-res.k*a.x;return res;
}
inline double calc(dl x,L a,L b)
{
return get_val(a,x)-get_val(b,x);
}
int r,m,n;
inline void input()
{
scanf("%d",&n);
rep(i,n)scanf("%lf",&p[i].x);
rep(i,n)scanf("%lf",&p[i].y);
}
inline void work()
{
rep(i,n-1)l[i]=get_line(p[i],p[i+1]);
m=n-1;sort(l+1,l+m+1);m=unique(l+1,l+m+1)-l-1;
rep(i,m)
{
while(r>1&&get_x(l[r],l[r-1])-get_x(l[r-1],l[i])>=0)r--;l[++r]=l[i];
}m=r;
int i=1,j=1;dl ans=1e30;
#define updata(x) ans=min(ans,calc(x,l[j],get_line(p[i],p[i+1])))
while(i1?get_x(l[j-1],l[j]):-INF);
dl R=(jp[i+1].x){i++;continue;}
if(R<p[i].x){j++;continue;}
updata(max(L,p[i].x));updata(min(R,p[i+1].x));
if(R<p[i+1].x)j++;
else i++;
}
if(n<=2)ans=0;
printf("%.3lf",ans);
}
int main()
{
//freopen("input.in","r",stdin);
input();
work();
return 0;
}