学习半平面交,刚开始把边界的现在的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;
}