计算几何 dls

实数比较

#define double db
const db EPS=1e-9;
int sign(db a){ return a<-EPS?-1:a>EPS };
int cmp(db a,db b){ return sign(a-b)};

点

struct P{db x,y;P(){}P(db _x,db _y):x(_x),y(_y){}P operator+(P p){ return {x+p.x,y+p.y}; }P operator-(P p){ return {x-p.x,y-p.y}; }P operator*(db d){ return {x*d,y*d}; }P operator/(db d){ return {x/d,y/d};}bool operator<(P p) const {int c=cmp(x,p.x);if(c) return c==-1;return cmp(y,p.y)==-1;} bool operator==(P o) const {return cmp(x,o.x)==0&&cmp(y,o.y)==0;}
}

点积和叉积

db dot(P p){ return x*p.x+y*p.y; }//点积
db det(P p){ return x*p.y-y*p.x; }//叉积

，，则点积·||·||·，当正，夹角为锐角，当负，夹角为钝角，当为0，两个向量互相垂直。在的投影长度为·。

叉积*||·||·sin<,> 当在的逆时针方向夹角为正， 当在顺时针方向夹角为负。则当叉积大于0时在的逆时针方向，小于0时在顺时针方向，等于0时和同向或反向。当点积·大于0时为同向，小于0时为反向。

当点积·大于0时，在以为x轴正方向的坐标系的一、三象限、当叉积*大于0时，在以为x轴正方向的坐标系的一、二象限。

以，组成三角形的面积S=1/2·|p|·|q|·=1/2·|*|。

极角排序

atan2(y,x); //返回值在(-180度,+180度)之间，用该函数获取每个向量的极角，再用sort排序即可
//缺点1：慢    缺点2：精度问题