计算几何初步模板

#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 1005
using namespace std;
const double eps = 1e-8, Pi = acos(-1), inf = 1e20;
struct Point 
{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){}
	inline Point operator + (const Point &p)const{return Point(x+p.x,y+p.y);}
	inline Point operator - (const Point &p)const{return Point(x-p.x,y-p.y);}
	inline Point operator * (const double &k)const{return Point(x*k,y*k);}
	inline double operator * (const Point &p)const{return x*p.x+y*p.y;}
	inline bool operator < (const Point &p)const{return x<p.x;}
	inline double angle(){return atan2(y,x);}
	inline void rotate(double ang){double xx=x*cos(ang)-y*sin(ang),yy=y*cos(ang)+x*sin(ang);x=xx,y=yy;}
}p[maxn];
typedef Point Vector;
struct Line
{
	Point P;
	Vector v;
	double ang;
	Line(Point P=Point(0,0),Vector v=Vector(0,0)):P(P),v(v){ang=v.angle();}
};
inline double sqr(double x){return x*x;}
inline int dcmp(double x){return fabs(x)<eps?0:x>0?1:-1;}
inline double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
inline bool Onleft(Line L,Point p){return dcmp(Cross(L.v,p-L.P))>0;}
inline double dist(Point a,Point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
inline Point GetInt(Line a,Line b){//求交点
	double t=Cross(b.v,(a.P-b.P))/Cross(a.v,b.v);
	return a.P+a.v*t;
}
int n;
double f(double x){
	return x;
	//modify according to problem.
}
inline double calc(double len,double fl,double fm,double fr){return (fl+4*fm+fr)*len/6;}
double Simpson(double l,double m,double r,double fl,double fm,double fr,double S)
{
	double m1=(l+m)/2,m2=(m+r)/2,fm1=f(m1),fm2=f(m2);
	double s1=calc(m-l,fl,fm1,fm),s2=calc(r-m,fm,fm2,fr);
	if(fabs(S-s1-s2)<=eps) return S;
	return Simpson(l,m1,m,fl,fm1,fm,s1)+Simpson(m,m2,r,fm,fm2,fr,s2);
}
void convex_hull(Point *a,Point *q)//凸包
{
	sort(a+1,a+1+n);
	int l=1,r=0;
	for(int i=1;i<=n;i++){
		while(l<r&&!Onleft(Line(q[r-1],q[r]-q[r-1]),a[i])) r--;
		q[++r]=a[i];
	}
	l=r;
	for(int i=n-1;i>=1;i--){
		while(l<r&&!Onleft(Line(q[r-1],q[r]-q[r-1]),a[i])) r--;
		q[++r]=a[i];
	}
}
/*
void HalfPlane()//半平面交
{
	sort(L+1,L+1+n);
	q[l=r=1]=L[1];
	for(int i=2;i<=n;i++)
	{
		while(l<r&&!Onleft(L[i],p[r-1])) r--;
		while(l<r&&!Onleft(L[i],p[l])) l++;
		q[++r]=L[i];
		if(dcmp(Cross(q[r].v,q[r-1].v))==0){
			r--;
			if(Onleft(q[r],L[i].P)) q[r]=L[i];
		}
		if(l<r) p[r-1]=GetInt(q[r],q[r-1]);
	}
	while(l<r&&!Onleft(q[l],p[r-1])) r--;
	//if(r-l<=1) ... 
	p[r]=GetInt(q[r],q[l]);
}
*/
int main()
{
	//input();
}