计算几何模板

超级大毒瘤

目前有仅有基本运算和求凸包以及面积
估计很快会加上半平面交&旋转卡(qia)壳(ke)
动态凸包……这辈子都不会有的（真香）

Debugging…

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define eps 1e-7
#define db double
using namespace std;
inline int sgn(db x){
	return fabs(x)<eps?0:(x>0?1:-1);
}

struct vec{ db x,y; };
typedef vec point;
inline bool cx(point a,point b){ return a.x<b.x; }

inline db dot(vec a,vec b){ return a.x*b.x+a.y*b.y; }
inline db crs(vec a,vec b){ return a.x*b.y-a.y*b.x; }
inline db l2(vec a){ return dot(a,a); }

inline vec operator+(vec a,vec b){ return (vec){a.x+b.x,a.y+b.y}; }
inline vec operator-(vec a,vec b){ return (vec){a.x-b.y,a.y-b.y}; }
inline vec operator*(vec a,db  x){ return (vec){a.x*x,a.y*x}; }
inline vec operator/(vec a,db  x){ return (vec){a.x/x,a.y/x}; }

inline db angle(vec a,vec b){
	return acos(dot(a,b)/sqrt(l2(a)*l2(b)));
}
inline vec rot(vec a,db c){
	return (vec){cos(c),sin(c)}*a.x+(vec){-sin(c),cos(c)}*a.y;
}

struct Segment{
	point a,b;
	inline vec operator~(){ return b-a; }
	inline db len(){ return sqrt(l2(b-a)); }
};
typedef Segment Line;

inline db dfptl(point p,Line x){ //distance from point to line
	return fabs(crs(p-x.a,~x)/x.len());
}
inline db dfpts(point p,Segment x){ //同上
	vec a=p-x.a,b=p-x.b,c=x.a-x.b;
	if(dot(a,c)<0) return sqrt(l2(a));
	if(dot(b,c)<0) return sqrt(l2(b));
	return fabs(crs(a,c)/x.len());
}
inline int cross(Segment x,Segment y){ //线段是否相交
	return sgn(crs(~x,y.a-x.a))*sgn(crs(~x,y.b-x.a))<0
		&& sgn(crs(~y,x.a-y.a))*sgn(crs(~y,x.b-y.a))<0;
}
inline point glp(Line x,Line y){ //直线交点
	vec u=x.a-y.a;
	db t=crs(~y,u)/crs(~x,~y);
	return x.a+(~x*t);
}
#define SIZE 110
struct Polygon{
	int n; point s[SIZE];
	inline int in(point x){
		vec y=(vec){1.3492e6,7.235792e5};
		Segment c=(Segment){x,y}; int A=0;
		for(int i=0;i<n;++i){
			if(!sgn(crs(x-s[i],x-s[i+1]))) return -1;
			A+=cross((Segment){s[i],s[i+1]},c);
		}
		return A;
	}
	inline db area(){
		db A=0;
		for(int i=1;i+1<n;++i)
			A+=crs(s[i]-s[0],s[i+1]-s[0]);
		return fabs(A/2);
	}
};
point q[SIZE];
inline void graham(point* s,int n){ //求凸包
	sort(s+1,s+1+n,cx); int t=0;
	for(int i=1;i<=n;++i){
		while(t>1 && sgn(crs(q[t-1]-q[t],s[i]-q[t-1]))<=0) --t;
		q[++t]=s[i];
	}
	int m=t;
	for(int i=n;i;--i){
		while(t>=m && sgn(crs(q[t-1]-q[t],s[i]-q[t-1]))<=0) --t;
		q[++t]=s[i];
	}
}