计算几何板子

#define i128 long long
inline i128 ABS(i128 x){return x<0?-x:x;}
struct frac{
	i128 x,y;
	frac(){}
	frac(i128 xx,i128 yy=1ll):x(xx),y(yy){
		if(y<0)x=-x,y=-y;
	}
	friend frac operator +(frac a,frac b){return frac(a.x*b.y+a.y*b.x,a.y*b.y);}
	friend frac operator -(frac a,frac b){return frac(a.x*b.y-a.y*b.x,a.y*b.y);}
	friend frac operator *(frac a,frac b){return frac(a.x*b.x,a.y*b.y);}
	friend frac operator /(frac a,frac b){return a*frac(b.y,b.x);}
	friend bool operator <(frac a,frac b){return a.x*b.y<b.x*a.y;}
	friend bool operator >(frac a,frac b){return a.x*b.y>b.x*a.y;}
	friend bool operator <=(frac a,frac b){return !(a>b);}
	friend bool operator >=(frac a,frac b){return !(a<b);}
	friend bool operator ==(frac a,frac b){return a.x*b.y==b.x*a.y;}
	friend bool operator !=(frac a,frac b){return !(a==b);}
	frac operator - () {return frac(0)-x;}
};

struct P{
	int x,y;
	P(int x=0,int y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(int o){return x*=o,y*=o,*this;}
	P&operator /=(int o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,int b){return a*=b;}
	friend P operator /(P a,int b){return a/=b;}
	friend bool operator <(P a,P b){return a.x==b.x?a.y<b.y:a.x<b.x;}
	friend int operator *(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend int operator %(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	inline double ang(){return atan2(y,x);}
	inline double l(){return sqrt((*this)*(*this));}
};

const double eps=1e-10,pi=3.14159265358979323846;
struct P{
	double x,y;
	P(double x=0,double y=0):x(x),y(y){}
	P&operator +=(P o){return x+=o.x,y+=o.y,*this;}
	P&operator -=(P o){return x-=o.x,y-=o.y,*this;}
	P&operator *=(double o){return x*=o,y*=o,*this;}
	P&operator /=(double o){return x/=o,y/=o,*this;}
	friend P operator +(P a,P b){return a+=b;}
	friend P operator -(P a,P b){return a-=b;}
	friend P operator *(P a,double b){return a*=b;}
	friend P operator /(P a,double b){return a/=b;}
	friend bool operator <(P a,P b){return fabs(a.x-b.x)<eps?a.y<b.y:a.x<b.x;}
	friend double operator *(P a,P b){return a.x*b.x+a.y*b.y;} // dot
	friend double operator %(P a,P b){return a.x*b.y-a.y*b.x;} // cross
	inline void spin(double o){double s=sin(o),c=cos(o),xx=x*c-y*s,yy=x*s-y*c;x=xx,y=yy;}
	inline double ang(){return atan2(y,x);}
	inline double l(){return sqrt((*this)*(*this));}
	void in(){cin>>x>>y;}
};
inline double d(P a,P b){return (a-b).l();}

struct line{
	P a,b;double c;
	line(){}
	line(P a,P b):a(a),b(b){c=b.ang();}
	friend P operator * (line a,line b){return a.a+a.b*(b.b%(a.a-b.a)/(a.b%b.b));}
	friend bool operator <(line a,line b){return fabs(a.c-b.c)<eps?(b.a-a.a)%a.b<0:a.c<b.c;}
};
P dir(line a){
	return a.b/(a.b.l());
}

double dis(line a,P b){
	return (((b-a.a)%a.b)/(a.b.l()));
}

struct cir{
	P o; double r;
	bool operator <(const cir&b)const{return r<b.r;}
};

vector<P>convex(vector<P>o){
	sort(o.begin(),o.end());
	int n=o.size();
	vector<P>p;
	For(i,0,n-1){
		while(p.size()>1&&(p.back()-p[p.size()-2])%(o[i]-p[p.size()-2])<eps) p.pop_back();
		p.pb(o[i]);
	}
	int m=p.size();
	Rep(i,n-2,0){
		while(p.size()>m&&(p.back()-p[p.size()-2])%(o[i]-p[p.size()-2])<eps) p.pop_back();
		if(i)p.pb(o[i]); 
	}
	return p;
}

vector<P>halfplane(vector<line>l)
{
	vector<P>res;
	sort(l.begin(),l.end());
	deque<P>p; deque<line>q;
	for(auto o:l){
		while(p.size()&&(p.back()-o.a)%o.b>0) q.pop_back(),p.pop_back();
		while(p.size()&&(p.front()-o.a)%o.b>0)q.pop_front(),p.pop_front();
		if (q.size()&&fabs(o.b%q.back().b)<eps){
			if (fabs(o.b.ang()-q.back().b.ang()) > eps)
				return p.clear(),res;
			q.pop_back(); if(p.size())p.pop_back();
		}
		if(q.size())p.pb(q.back()*o); q.pb(o); 
	}
	while(p.size()&&(p.back()-q.front().a)%(q.front().b)>0)
		q.pop_back(),p.pop_back();
	if(q.size()<3)p.clear();
	else p.pb(q.front()*q.back());
	while(p.size())res.pb(p.front()),p.pop_front();
	return res;
}