学习半平面交,刚开始把边界的现在的1e6打了1e100于是爆炸...

//By Richard
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define log2(x) (31-__builtin_clz(x))
#define mod (int)(1e9+7)
#define inf 0x3f3f3f3f
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
#ifdef ONLINE_JUDGE
#define debugdo(X)
#define debugndo(X)
#define debugout(X)
#endif
#define putarray(x,n) rep(iiii,1,n) printf("%d ",x[iiii])
#define mp make_pair
using namespace std;
typedef pair<int,int> pairs;
typedef long long LL;
/////////////////////read4.0////////////////////////////////////
template <typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template <typename T>
inline void read(T &x,T &y){read(x);read(y);}
template <typename T>
inline void read(T &x,T &y,T &z){read(x);read(y);read(z);}
/////////////////variables&functions////////////////////
const int maxn=301;
const double eps=0.000000000001;
int n,cnt;
#define angel angle
struct Point
{
    double x,y;
    Point(int a,int b):x((double)a),y((double)b){}
    Point(double a=0,double b=0):x(a),y(b){}
    inline Point operator-(Point b)const{return Point(x-b.x,y-b.y);}
    inline double operator*(Point b)const{return x*b.y-y*b.x;}
}res[maxn],p[maxn];
double mul(Point x,Point y,Point z){return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);}
struct Line
{
    Point x,y;
    double angle;
    Line(Point a=Point(0,0),Point b=Point(0,0),double e=0):x(a),y(b),angle(e){}
    inline bool operator<(Line b)const{return abs(angle-b.angle)<eps?mul(x,b.x,b.y)>0:angel<b.angel;}
    inline bool operator==(Line b)const{return abs(angel-b.angle)<eps;}
}data[maxn];
struct deque
{
    int top,bot,data[maxn];
    ~deque(){top=1;bot=0;}
    inline int front(){return data[bot];}
    inline int front2(){return data[bot+1];}
    inline int back(){return data[top-1];}
    inline int back2(){return data[top-2];}
    inline void pop_front(){bot++;}
    inline void pop_back(){top--;}
    inline bool empty(){return top<=bot;}
    inline void push_front(int x){data[--bot]=x;}
    inline void push_back(int x){data[top++]=x;}
    inline bool judge(){return top>bot+1;}
    inline bool judge2(){return top>bot+2;}
}deq;
Point intersect(Line a,Line b)
{
    double k1,k2,t;
    k1=(b.y-a.x)*(a.y-a.x);
    k2=(a.y-a.x)*(b.x-a.x);
    t=k1/(k1+k2);
    return Point(b.y.x+(b.x.x-b.y.x)*t,b.y.y+(b.x.y-b.y.y)*t);
}
inline bool judge(Line x,Line y,Line z)
{
    Point temp=intersect(x,y);
    return (z.y-z.x)*(temp-z.x)<0;
}
void hpi(Line *a,int n)//Half-Plane Intersection
{
    sort(a+1,a+n+1);
    int m=unique(a+1,a+n+1)-a-1;
    deq.push_back(1);deq.push_back(2);
    rep(i,3,m)
    {
        while (deq.judge()&&judge(a[deq.back2()],a[deq.back()],a[i])) deq.pop_back();
        while (deq.judge()&&judge(a[deq.front2()],a[deq.front()],a[i])) deq.pop_front();
        deq.push_back(i);
    }
    while (deq.judge2()&&judge(a[deq.back2()],a[deq.back()],a[deq.front()])) deq.pop_back();
    while (deq.judge2()&&judge(a[deq.front2()],a[deq.front()],a[deq.back()])) deq.pop_front();
    deq.push_back(deq.front());
//  rep(i,deq.bot,deq.top-1) printf("%lf %lf %lf %lf\n",a[deq.data[i]].x.x,a[deq.data[i]].x.y,a[deq.data[i]].y.x,a[deq.data[i]].y.y);
    rep(i,deq.bot,deq.top-2) res[++cnt]=intersect(a[deq.data[i]],a[deq.data[i+1]]);
}
int main()
{
    read(n);
    rep(i,1,n) read(p[i].x);
    rep(i,1,n) read(p[i].y);
    p[0]=Point((double)p[1].x,1e6);
    p[n+1]=Point((double)p[n].x,1e6);
    double beforex=p[0].x,beforey=p[0].y;
    //data[1]=Line(Point(),Point(beforex,beforey));
    rep(i,1,n+1) 
    {
//      if (y[i]>=beforey) 

    data[i]=Line(Point(beforex,beforey),Point(p[i].x,p[i].y),atan2(p[i].y-beforey,p[i].x-beforex));

// else data[i-1]=Line(Point(x[i],y[i]),Point(beforex,beforey),atan2(beforey-y[i],beforex-x[i]));
beforex=p[i].x;beforey=p[i].y;
}
//data[n+1]=Line(Point(beforex,beforey),Point();
hpi(data,n+1);
double ans=1e18;
rep(i,1,cnt)
{
rep(j,1,n-1)
{
Point t(res[i].x,(double)(-1));
if (res[i].x>p[j].x&&res[i].x<=p[j+1].x) ans=min(ans,res[i].y-intersect(Line(p[j],p[j+1]),Line(t,res[i])).y);
}
}
rep(i,1,n)
rep(j,1,cnt-1)
{
Point t(p[i].x,(double)(-1));
if (p[i].x>res[j].x&&p[i].x<=res[j+1].x) ans=min(ans,intersect(Line(res[j],res[j+1]),Line(t,p[i])).y-p[i].y);
}
printf("%.3lf\n",ans);
return 0;
}