/*    题目大意：给出平面上一些点，问一个半径为1的圆最多可以覆盖几个点    题解：我们对于每个点画半径为1的圆，那么在两圆交弧上的点所画的圆，一定可以覆盖这两个点    我们对于每个点计算出其和其它点的交弧，对这些交弧计算起末位置对于圆心的极角，    对这些我们进行扫描线操作，统计最大交集数量就是答案。*/#include <cstdio>#include <algorithm>#include <cmath> #include <cstring>using namespace std;double EPS=1e-10;double add(double a,double b){    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;    return a+b;}const int MAX_N=310;struct P{    double x,y;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(add(x,p.x),add(y,p.y));}    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}    P operator * (double d){return P(x*d,y*d);}    double dot(P p){return add(x*p.x,y*p.y);} //点积    double det(P p){return add(x*p.y,-y*p.x);}  //叉积}ps[MAX_N];double dist(P p,P q){return sqrt((p-q).dot(p-q));}struct PolarAngle{    double angle;    bool flag;}as[MAX_N];bool cmp_a(PolarAngle a,PolarAngle b){	return a.angle<b.angle;}int solve(int n,double r){    int ans=1;    for(int i=0;i<n;i++){        int m=0; double d;        for(int j=0;j<n;j++){            if(i!=j&&(d=dist(ps[i],ps[j]))<=2*r){                double phi=acos(d/2);                double theta=atan2(ps[j].y-ps[i].y,ps[j].x-ps[i].x);                as[m].angle=theta-phi,as[m++].flag=1;                as[m].angle=theta+phi,as[m++].flag=0;            }        }sort(as,as+m,cmp_a);        for(int sum=1,j=0;j<m;j++){            if(as[j].flag)sum++;            else sum--;            ans=max(ans,sum);        }    }return ans;}int N;int main(){    while(scanf("%d",&N),N){        for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);        printf("%d\n",solve(N,1.0));    }return 0;}

/*    给出一些圆的位置和半径以及叠放次序，问能看到的有几个圆*/#include <cstring>#include <algorithm>#include <cmath>#include <complex>#include <vector>#include <cstdio> using namespace std;typedef complex<double> P;#define M_PI 3.14159265358979323846const double EPS=4E-13;double Tran(double r){    while(r<0.0)r+=2*M_PI;    while(r>=2*M_PI)r-=2*M_PI;    return r;}int hit_test(P p,vector<P>&points,vector<double> &rs){    for(int i=rs.size()-1;i>=0;i--){        if(abs(points[i]-p)<rs[i])return i;    }return -1;}int n;int main(){    while(scanf("%d",&n),n){        vector<P> points;        vector<double> rs;        for(int i=0;i<n;i++){            double x,y,r;            scanf("%lf%lf%lf",&x,&y,&r);            points.push_back(P(x,y));            rs.push_back(r);        }vector<bool> visible(n,false);        for(int i=0;i<n;i++){            vector<double> rads;            rads.push_back(0.0);            rads.push_back(2.0*M_PI);            for(int j=0;j<n;j++){                double a=rs[i],b=abs(points[j]-points[i]),c=rs[j];                if(a+b<c||a+c<b||b+c<a)continue;                double d=arg(points[j]-points[i]);                double e=acos((a*a+b*b-c*c)/(2*a*b));                rads.push_back(Tran(d+e));                rads.push_back(Tran(d-e));            }sort(rads.begin(),rads.end());			      for(int j=0;j<rads.size()-1;j++){				        double rad=(rads[j+1]+rads[j])/2.0;				        for(int k=-1;k<=1;k+=2){					          int t=hit_test(P(points[i].real()+(rs[i]+EPS*k)*cos(rad),points[i].imag()+(rs[i]+EPS*k)*sin(rad)),points,rs);					          if(t!=-1)visible[t]=true;				        }			      }        }printf("%d\n",count(visible.begin(),visible.end(),true));    }return 0;}

/*    题目大意：给出一些圆，求一条直线最多与几个圆相切    题解：我们枚举任意两个圆的切线，然后计算与这条切线相切的圆的数目即可。*/#include <iostream>#include <vector>#include <complex>#include <cmath>#include <algorithm>using namespace std;typedef complex<double> P;const double PI=acos(-1);const double EPS=1e-12;int cmp(double a,double b){	  const double diff=a-b;	  if(fabs(diff)<EPS)return 0;	  else if(diff<0)return -1;	  else return 1;}inline double dot(const P &a, const P &b){	  return a.real()*b.real()+a.imag()*b.imag();}inline double cross(const P &a, const P &b){    return a.real()*b.imag()-b.real()*a.imag();}struct line{    P a,b;    line(){}    line(const P &p,const P &q):a(p),b(q){}	  // 是否平行	  inline bool parallel(const line &ln) const{		    return abs(cross(ln.b-ln.a,b-a))<EPS;			    //平行叉乘得到向量的模是0，也就是sin(theta)=0<->theta=0	  }	  // 是否相交	  inline bool intersects(const line &ln) const{		    return !parallel(ln);	  }	  // 求交点	  inline P intersection(const line &ln) const{	      const P x=b-a;	      const P y=ln.b-ln.a;	      return a+x*(cross(y,ln.a-a))/cross(y,x);	  }	  // 点到直线的距离	  inline double distance(const P &p) const{	      return abs(cross(p-a,b-a))/abs(b-a);	  }	  // 求垂足坐标	  inline P perpendicular(const P &p) const{	      const double t=dot(p-a,a-b)/dot(b-a,b-a);		    return a+t*(a-b);		}};struct circle{    P o;    double r;    circle(){}    circle(const P &p,double x):o(p),r(x){}    // 通过点 p 的两条切线    pair<P,P> tangent(const P &p)const{        const double L=abs(o-p);        const double M=sqrt(L*L-r*r);        const double theta=asin(r/L);        const P v=(o-p)/L;        return make_pair(p+M*(v*polar(1.0,theta)),p+M*(v*polar(1.0,-theta)));	  }	  // 两个半径相等圆的两条平行外切线	  pair<line,line> outer_tangent_parallel(const circle &c) const{	      const P d=o-c.o;	      const P v=d*P(0,1)*r/abs(d);	      return make_pair(line(o+v,c.o+v),line(o-v,c.o-v));	  }	  // 两个圆外切线	  pair<line,line> outer_tangent(const circle &c) const{	      if(cmp(r,c.r)==0)return outer_tangent_parallel(c);	      if(r>c.r)return c.outer_tangent(*this);	      const P d=o-c.o;	      const double fact=c.r/r-1;	      const P base=c.o+d+d/fact;	      const pair<P, P> t=tangent(base);	      return make_pair(line(base,t.first),line(base,t.second));	  }	  // 内切线	  pair<line,line> inner_tangent(const circle &c) const{	      if(r>c.r)return c.inner_tangent(*this);	      const P d=c.o-o;	      const double fact=c.r/r+1;	      const P base=o+d/fact;	      const pair<P,P> t=tangent(base);	      return make_pair(line(base,t.first),line(base,t.second));	  }	  // 是否相交	  inline bool intersects(const circle &c) const{		    return !contains(c)&&!c.contains(*this)&&cmp(abs(o-c.o),r+c.r)<=0;	  }	  // 是否相离	  inline bool independent(const circle &c) const{	      return cmp(abs(o-c.o),r+c.r)>0;	  }	  // 两个圆的交点	  pair<P,P> intersection(const circle &c) const{	      const double d=abs(o-c.o);	      const double cos_=(d*d+r*r-c.r*c.r)/(2*d);	      const double sin_=sqrt(r*r-cos_*cos_);	      const P e=(c.o-o)/d;	      return make_pair(o+e*P(cos_,sin_),o+e* P(cos_,-sin_));	  }	  // 是否包含圆c	  inline bool contains(const circle &c) const{	      return cmp(abs(o-c.o)+c.r,r)<0;	  }	  // 是否相交	  inline bool intersects(const line &ln) const{	      return cmp(abs(ln.distance(o)),r)<=0;	  }	  // 圆心到直线的距离	  inline double distance(const line &ln) const{		    return abs(ln.distance(o));	  }	  // 圆与直线的交点	  pair<P,P> intersection(const line &ln) const{	      const P h=ln.perpendicular(o);	      const double d=abs(h-o);	      P ab=ln.b-ln.a;	      ab/=abs(ab);	      const double l=sqrt(r*r-d*d);	      return make_pair(h+l*ab,h-l*ab);	  }};void enum_event(const circle &c1,const circle &c2,vector<line> &lines){	  if(c1.independent(c2)){		    pair<line,line> outer=c1.outer_tangent(c2);		    lines.push_back(outer.first);		    lines.push_back(outer.second);		    pair<line,line> inner = c1.inner_tangent(c2);		    lines.push_back(inner.first);		    lines.push_back(inner.second);		}else if (c1.intersects(c2)){		    pair<line,line> outer=c1.outer_tangent(c2);		    lines.push_back(outer.first);		    lines.push_back(outer.second);		    pair<P,P> inter=c1.intersection(c2);		    lines.push_back(line(inter.first,inter.second));			    // 此时内切线不存在，使用交点形成的线代替		}}bool solve(){    int N;    scanf("%d",&N);    if(!N)return false;    vector<pair<circle,circle> > jewels;    vector<line> lines;    for(int i=0;i<N;i++){        double x,y,r,m;        scanf("%lf%lf%lf%lf",&x,&y,&r,&m);        const P center(x,y);        pair<circle,circle> jewel=make_pair(circle(center,r),circle(center,r+m));        for(const auto &other:jewels){            enum_event(jewel.first,other.first,lines);            enum_event(jewel.first,other.second,lines);            enum_event(jewel.second,other.first,lines);            enum_event(jewel.second,other.second,lines);        }jewels.push_back(jewel);    }int ans=1;    for(auto &l:lines){        int cnt=count_if(jewels.begin(),jewels.end(),[&](const pair<circle,circle> &j){	// [&] 按引用捕获在lambda表达式所在函数的函数体中提及的全部自动储存持续性变量            return cmp(j.first.r, j.first.distance(l))<=0&&cmp(j.second.r,j.second.distance(l))>=0;	// 在磁力圆范围内且不在本体范围内        });        ans=max(ans, cnt);    }printf("%d\n",ans);    return 1;}int main(){	  while(solve());	  return 0;}

/*    题目大意：给出一些矩形，没有相交和包含的情况，只有相切的情况    问有多少个矩形没有相切或者边角重叠    题解：我们将所有的与x轴平行的线段和与y周平行的线段分开处理，判断是否出现重合    对重合的两个矩形进行标识，最后没有被标识过的矩形数目就是答案。*/#include <cstdio>#include <vector>#include <algorithm>#include <cstring>using namespace std;const int N=30010;struct data{    int id,d,x,y;    data(){};     data(int _d,int _x,int _y,int _id):d(_d),x(_x),y(_y),id(_id){}};vector<data> sx,sy;bool vis[N];bool cmp(data a,data b){    if(a.d!=b.d)return a.d<b.d;    if(a.x!=b.x)return a.x<b.x;    return a.y<b.y;}int n,a,b,c,d;void solve(){    sx.clear();sy.clear();    memset(vis,0,sizeof(vis));    for(int i=0;i<n;i++){        scanf("%d%d%d%d",&a,&b,&c,&d);        sy.push_back(data(b,a,c,i));        sy.push_back(data(d,a,c,i));          sx.push_back(data(a,b,d,i));          sx.push_back(data(c,b,d,i));    }sort(sx.begin(),sx.end(),cmp);    sort(sy.begin(),sy.end(),cmp);    int t=sy[0].y;    for(int i=1;i<sy.size();i++){        if(sy[i-1].d==sy[i].d){            if(t>=sy[i].x){                vis[sy[i].id]=vis[sy[i-1].id]=1;            }        }else t=sy[i].y;        t=max(sy[i].y,t);    }t=sx[0].y;    for(int i=1;i<sx.size();i++){        if(sx[i-1].d==sx[i].d){            if(t>=sx[i].x){                vis[sx[i].id]=vis[sx[i-1].id]=1;            }        }else t=sx[i].y;        t=max(sx[i].y,t);    }int ans=0;    for(int i=0;i<n;i++)if(!vis[i])ans++;    printf("%d\n",ans);}int main(){    while(~scanf("%d",&n))solve();    return 0;}

/*    题目大意：给出一些点，每个点只能向外引出一条平行X轴，和Y轴的边，    问能否构成一个闭多边形，如果能，返回多边形的总边长，否则返回-1    题解：我们发现对于每一行或者每一列都必须有偶数个点，且两两之间相邻才能满足条件    所以我们将其连线之后判断是否可以构成一个封闭图形，同时还需要判断这些线是否会相交，    如果相交即不成立*/#include <cstdio>#include <algorithm>using namespace std;const int N=100010; struct Point{int x,y,id;}p[N];struct Line{    int d,x,y;    Line(){}    Line(int _d,int _x,int _y):d(_d),x(_x),y(_y){}}l[N];int cmp_x(Point a,Point b){    if(a.x==b.x)return a.y<b.y;    return a.x<b.x;}int cmp_y(Point a,Point b){    if(a.y==b.y)return a.x<b.x;    return a.y<b.y;}int con[N][2],n,ln,T;int Check(Point a,Point b){    int y=a.y,x1=a.x,x2=b.x;    for(int i=0;i<ln;i++){        if(x1<l[i].d&&x2>l[i].d&&l[i].x<y&&l[i].y>y)return 1;    }return 0;}int main(){    scanf("%d",&T);    while(T--){        scanf("%d",&n);        for(int i=0;i<n;i++){            scanf("%d%d",&p[i].x,&p[i].y);            p[i].id=i;        }int s=0,cnt=1,flag=0;        ln=0;        sort(p,p+n,cmp_x);        for(int i=1;i<n&&!flag;i++){            if(p[i].x!=p[i-1].x){                if(cnt&1)flag=1;                cnt=1;            }else{                cnt++;                if((cnt&1)==0){                    s+=p[i].y-p[i-1].y;                    con[p[i].id][0]=p[i-1].id;                    con[p[i-1].id][0]=p[i].id;                    l[ln++]=Line(p[i].x,p[i-1].y,p[i].y);                }            }        }sort(p,p+n,cmp_y);        cnt=1;        for(int i=1;i<n&&!flag;i++){            if(p[i].y!=p[i-1].y){                if(cnt&1)flag=1;                cnt=1;            }            else{                cnt++;                if((cnt&1)==0){                    s+=p[i].x-p[i-1].x;                    con[p[i].id][1]=p[i-1].id;                    con[p[i-1].id][1]=p[i].id;                    if(Check(p[i-1],p[i]))flag=1;                }            }        }int t=1,x=0,c=0;        for(;;){            x=con[x][t];            t^=1; c++;            if(x==0||flag)break;        }if(c!=n)flag=1;        if(flag)puts("-1");        else printf("%d\n",s);    }return 0;}

/*    题目大意：给出一些点的二维坐标和权值，求用一个长H，宽W的矩形能框住的最大权值之和，    在矩形边缘的点不计算在内    题解：我们计算能扫到这个点的区间范围，将其拆分为两条平行于y轴的左闭右开的直线，    为方便边界处理，我们将坐标扩大两倍，之后我们按照x轴对这些线段进行扫描    统计出现的最大值即可。*/#include <cstdio>#include <algorithm>#include <utility>using namespace std;typedef long long LL;const int N=10010;LL xs[N],ys[N],X[N<<1],Y[N<<1];int cs[N],tag[N<<3],T[N<<3];pair<pair<int,int>,pair<int,int> >event[N<<1];void update(int L,int R,int v,int x,int l,int r){    if(L<=l&&r<=R){T[x]+=v;tag[x]+=v;return;}    int mid=(l+r)>>1;    if(L<=mid)update(L,R,v,x<<1,l,mid);    if(mid<R)update(L,R,v,x<<1|1,mid+1,r);    T[x]=max(T[x<<1],T[x<<1|1])+tag[x];}int n,W,H;void solve(){    for(int i=0;i<n;i++){        scanf("%lld%lld%d",xs+i,ys+i,cs+i);        xs[i]<<=1; ys[i]<<=1;    }    for(int i=0;i<n;i++){        X[i<<1]=xs[i]-W; X[i<<1|1]=xs[i]+W;        Y[i<<1]=ys[i]-H; Y[i<<1|1]=ys[i]-1+H;    }sort(X,X+n*2);sort(Y,Y+n*2);    for(int i=0;i<n;i++){        event[i<<1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]-W)-X,cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));        event[i<<1|1]=make_pair(make_pair(lower_bound(X,X+n*2,xs[i]+W)-X,-cs[i]),make_pair(lower_bound(Y,Y+n*2,ys[i]-H)-Y,lower_bound(Y,Y+n*2,ys[i]+H-1)-Y));    }sort(event,event+n*2);		int ans=0;		for(int i=0;i<n*2;i++){				  update(event[i].second.first,event[i].second.second,event[i].first.second,1,0,n*2);			  ans=max(ans,T[1]);		}printf("%d\n",ans);}int main(){    while(~scanf("%d%d%d",&n,&W,&H))solve();    return 0;}

/*    题目大意：给出一个城堡，要求求出距城堡距离大于L的地方建围墙将城堡围起来求所要围墙的长度    题解：画图易得答案为凸包的周长加一个圆的周长。*/#include <cstdio>#include <algorithm>#include <cmath>#include <vector>using namespace std;double EPS=1e-10;const double PI=acos(-1.0);double add(double a,double b){    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;    return a+b;}struct P{    double x,y;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(add(x,p.x),add(y,p.y));}    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}    P operator * (double d){return P(x*d,y*d);}    double dot(P p){return add(x*p.x,y*p.y);} //点积    double det(P p){return add(x*p.y,-y*p.x);}  //叉积};bool cmp_x(const P& p,const P& q){    if(p.x!=q.x)return p.x<q.x;    return p.y<q.y;  }vector<P> convex_hull(P* ps,int n){    sort(ps,ps+n,cmp_x);    int k=0;    vector<P> qs(n*2);    for(int i=0;i<n;i++){        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }    for(int i=n-2,t=k;i>=0;i--){        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }qs.resize(k-1);    return qs;}double dist(P p,P q){return sqrt((p-q).dot(p-q));}const int MAX_N=1000;int N,L;P ps[MAX_N];vector<P> con;void solve(){    for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);    con=convex_hull(ps,N);    double res=0;    for(int i=0;i<con.size()-1;i++)res+=dist(con[i],con[i+1]);    res+=dist(con[0],con[con.size()-1]);    res+=2*PI*L;    printf("%d\n",(int)(res+0.5));}int main(){    while(~scanf("%d%d",&N,&L))solve();    return 0;}

/*    题目大意：给出一些点，表示一些屋子，这些屋子共同组成了村庄，现在要建一些高速公路    问是否经过了村庄。    题解：这些屋子的关键点一定在凸包上，所以我们只要求出凸包，判断是否和线相交即可    我们求出与高速公路相近和近似相反的向量，判断连线是否与这条公路相交即可。*/#include <cstdio>#include <algorithm>#include <cmath>#include <vector>using namespace std;double EPS=1e-10;const double PI=acos(-1.0);double add(double a,double b){    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;    return a+b;}struct P{    double x,y;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(add(x,p.x),add(y,p.y));}    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}    P operator * (double d){return P(x*d,y*d);}    double dot(P p){return add(x*p.x,y*p.y);} //点积    double det(P p){return add(x*p.y,-y*p.x);}  //叉积};bool cmp_x(const P& p,const P& q){    if(p.x!=q.x)return p.x<q.x;    return p.y<q.y;  }vector<P> convex_hull(P* ps,int n){    sort(ps,ps+n,cmp_x);    int k=0;    vector<P> qs(n*2);    for(int i=0;i<n;i++){        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }    for(int i=n-2,t=k;i>=0;i--){        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }qs.resize(k-1);    return qs;}double dist(P p,P q){return sqrt((p-q).dot(p-q));}double normalize(double r){	  if(r<-PI/2.0+EPS)r+=PI*2;	  return r;}double atan2(const P& p){    return normalize(atan2(p.y, p.x));}bool double_cmp(double a,double b){    return a+EPS<b;}const int MAX_N=100010;int N,n;P ps[MAX_N];double as[MAX_N];void solve(){    for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);    vector<P> chs;    if(N>1){        chs=convex_hull(ps,N);        n=chs.size();        chs.push_back(chs[0]);    }    for(int i=0;i<n;i++)as[i]=atan2(chs[i+1]-chs[i]);    sort(as,as+n,double_cmp);    P p1,p2;    while(~scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y)){        if(N<2){puts("GOOD");continue;}        int x=upper_bound(as,as+n,atan2(p2-p1),double_cmp)-as;        int y=upper_bound(as,as+n,atan2(p1-p2),double_cmp)-as;        puts((((p2-p1).det(chs[x]-p1)*(p2-p1).det(chs[y]-p1)>-EPS))?"GOOD":"BAD");    }}int main(){    while(~scanf("%d",&N))solve();    return 0;}

/*    题目大意：求出两个凸包之间的最短距离    题解：我们先找到一个凸包的上顶点和一个凸包的下定点，以这两个点为起点向下一个点画线，    做旋转卡壳，答案一定包含在这个过程中*/#include <cstdio>#include <algorithm>#include <cmath>#include <vector>using namespace std;double EPS=1e-10;const double INF=0x3F3F3F3F;const double PI=acos(-1.0);double add(double a,double b){    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;    return a+b;}struct P{    double x,y;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(add(x,p.x),add(y,p.y));}    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}    P operator * (double d){return P(x*d,y*d);}    double dot(P p){return add(x*p.x,y*p.y);} //点积    double det(P p){return add(x*p.y,-y*p.x);}  //叉积};bool cmp_y(const P& p,const P& q){    if(p.y!=q.y)return p.y<q.y;    return p.x<q.x;  }double dist(P p,P q){return sqrt((p-q).dot(p-q));}double cross(P a, P b,P c){return(b-a).det(c-a);}double multi(P a,P b,P c){return(b-a).dot(c-a);}// 点到线段距离 double point_to_line(P a,P b,P c){    if(dist(a,b)<EPS)return dist(b,c);    if(multi(a,b,c)<-EPS)return dist(a,c);    if(multi(b,a,c)<-EPS)return dist(b,c);    return fabs(cross(a,b,c)/dist(a,b));}// 线段到线段距离 double line_to_line(P A,P B,P C,P D){    double a=point_to_line(A,B,C);    double b=point_to_line(A,B,D);    double c=point_to_line(C,D,A);    double d=point_to_line(C,D,B);    return min(min(a,b),min(c,d));}void anticlockwise_sort(P* p,int N){    for(int i=0;i<N-2;i++){        double tmp=cross(p[i],p[i+1],p[i+2]);        if(tmp>EPS)return;        else if(tmp<-EPS){            reverse(p,p+N);            return;        }    }}const int MAX_N=10000;int n,m;P ps[MAX_N],qs[MAX_N];void solve(){    for(int i=0;i<n;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);    for(int i=0;i<m;i++)scanf("%lf%lf",&qs[i].x,&qs[i].y);    anticlockwise_sort(ps,n);		anticlockwise_sort(qs,m);		int i=0,j=0;		for(int k=0;k<n;k++)if(!cmp_y(ps[i],ps[k]))i=k;    for(int k=0;k<n;k++)if(cmp_y(qs[j],qs[k]))j=k;    double res=INF;    ps[n]=ps[0]; qs[m]=qs[0];    for(int k=0;k<n;k++){    	while(cross(ps[i+1],qs[j+1],ps[i])-cross(ps[i+1],qs[j],ps[i])>EPS)j=(j+1)%m;        res=min(res,line_to_line(ps[i],ps[i+1],qs[j],qs[j+1]));        i=(i+1)%n;    }printf("%.5lf\n",res);	}int main(){    while(~scanf("%d%d",&n,&m)&&n+m)solve();    return 0;}

/*    题目大意：给出一些点，求出能组成的最大面积的三角形    题解：最大三角形一定位于凸包上，因此我们先求凸包，再在凸包上计算，    因为三角形在枚举了一条固定边之后，图形面积随着另一个点的位置变换先变大后变小    因此我们发现面积递减之后就移动固定边。*/#include <cstdio>#include <algorithm>#include <cmath>#include <vector>using namespace std;double EPS=1e-10;const double PI=acos(-1.0);double add(double a,double b){    if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;    return a+b;}struct P{    double x,y;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(add(x,p.x),add(y,p.y));}    P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}    P operator * (double d){return P(x*d,y*d);}    double dot(P p){return add(x*p.x,y*p.y);} //点积    double det(P p){return add(x*p.y,-y*p.x);}  //叉积};bool cmp_x(const P& p,const P& q){    if(p.x!=q.x)return p.x<q.x;    return p.y<q.y;  }vector<P> convex_hull(P* ps,int n){    sort(ps,ps+n,cmp_x);    int k=0;    vector<P> qs(n*2);    for(int i=0;i<n;i++){        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }    for(int i=n-2,t=k;i>=0;i--){        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }qs.resize(k-1);    return qs;}double cross(P A,P B,P C){return(B-A).det(C-A);}const int MAX_N=50010;int N;P ps[MAX_N];void solve(){    for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);    vector<P> qs=convex_hull(ps,N);    N=qs.size(); int ans=0;    for(int i=1;i<(N+1)/2;i++){ //枚举跨度         int p1=(i+1)%N;        for(int p3=0;p3<N;p3++){            int p2=(p3+i)%N;            int prev=abs(cross(qs[p3],qs[p2],qs[p1]));            for(++p1;p1!=p2&&p1!=p3;++p1){                if(p1==N)p1=0;                int cur=abs(cross(qs[p3],qs[p2],qs[p1]));                ans=max(ans,prev);                if(cur<=prev)break;                prev=cur;            }--p1;            if(p1==-1)p1+=N;        }    }printf("%d.%s\n",ans/2,ans%2==1?"50":"00");}int main(){    while(~scanf("%d",&N)&&N>0)solve();    return 0;}

/*    题目大意:给出一些点，请删去一个点，使得包围这些点用的线长最短    题解：去掉的点肯定是凸包上的点，所以枚举凸包上的点去掉，再计算面积即可。*/#include <cstdio>#include <algorithm>#include <cmath>#include <vector>#include <cstring>using namespace std;struct P{    int x,y;    int id;    P(){}    P(double x,double y):x(x),y(y){}    P operator + (P p){return P(x+p.x,y+p.y);}    P operator - (P p){return P(x-p.x,y-p.y);}    P operator * (double d){return P(x*d,y*d);}    int dot(P p){return x*p.x+y*p.y;} //点积    int det(P p){return x*p.y-y*p.x;}  //叉积};bool cmp_x(const P& p,const P& q){    if(p.x!=q.x)return p.x<q.x;    return p.y<q.y;  }vector<P> convex_hull(P* ps,int n){    sort(ps,ps+n,cmp_x);    int k=0;    vector<P> qs(n*2);    for(int i=0;i<n;i++){        while((k>1)&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }    for(int i=n-2,t=k;i>=0;i--){        while(k>t&&(qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1])<=0)k--;        qs[k++]=ps[i];    }qs.resize(k-1);    return qs;}int cross(P a, P b,P c){return(b-a).det(c-a);}int compute_area(P A,P B,P C){    int res=cross(A,B,C);    if(res<0){return -res;}    return res;}int compute_area(const vector<P>& ps){    int total=0;    for(int i=2;i<ps.size();i++){        total+=compute_area(ps[0],ps[i-1],ps[i]);    }return total;}const int MAX_N=100010;int N;P p[MAX_N],q[MAX_N];void solve(){    for(int i=0;i<N;i++){        scanf("%d%d",&p[i].x,&p[i].y);        p[i].id=i;    }memcpy(q,p,N*sizeof(P));    vector<P> ps=convex_hull(p,N);    int ans=0x3f3f3f3f;    for(int i=0;i<ps.size();i++){        memcpy(p,q,N*sizeof(P));        swap(p[ps[i].id],p[N-1]);        ans=min(ans,compute_area(convex_hull(p,N-1)));    }printf("%d.%s\n",ans/2,ans%2==1?"50":"00");}int main(){    while(~scanf("%d",&N),N)solve();    return 0;}