计算几何基础整合（Point类）

本篇专讲计算几何基础，然后贴板子。
本文中用 $\vec v$ 表示向量 $v$，用$\times$表示叉积，$\cdot$ 表示点积。

首先定义Point类：

const double eps=1e-8;

int dcmp(double x) {return fabs(x)<=eps?0:x>eps?1:-1;}

struct Point {
	double x,y;
	Point(double x=0,double y=0):x(x),y(y) {}
	Point operator + (const Point &a) {return Point(x+a.x,y+a.y);}
	Point operator - (const Point &a) {return Point(a.x-x,a.y-y);} //注意翻转！！
	Point operator * (double a) {return Point(x*a,y*a);}
	Point operator / (double a) {return Point(x/a,y/a);}
	bool operator < (const Point &b) const {return x<b.x||(x==b.x&&y<b.y);}
	bool operator == (Point b) {return dcmp(x-b.x)==0&&dcmp(y-b.y)==0;}
	double length() {return sqrt(x*x+y*y);}
	Point rotate(double rad) {return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));} //逆时针
	Point normal(Point a) {return Point(-a.y/a.length(),a.x/a.length());} //长度归一
};

typedef Point Vector; //仅为了写法方便，但意义不同

值得注意的是，在重载减法的时候，为了代码方便将其反过来定义了，这样$a-b$就表示$a\rightarrow b$这个向量。但如果要用到减法时请将它翻转回去。

类中定义了两个操作：

向量旋转
根据仿射变换，逆时针旋转$\alpha$度时需要执行： $\begin{bmatrix} \cos(\alpha) & \sin(\alpha) & 0 \\ \sin(\alpha) & \cos(\alpha) & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ 1 \end{bmatrix}$
长度归一
这是方向向量的一种定义方法，向量只有方向没有长度。

然后是叉积点积，夹角以及三角形面积

double Cross(const Vector& a,const Vector& b) {return a.x*b.y-b.x*a.y;}
double Dot(Vector a,Vector b) {return a.x*b.x+a.y*b.y;}
double Angle(Vector a,Vector b) {return acos(Dot(a,b)/a.length()/b.length());}
double Area(Point a,Point b,Point c) {return Cross(b-a,c-a);}

判断$p$是否在线段上
通过叉积判断面积是否为$0$，也就是判断是否在直线上。
通过点积判断投影是否小于$0$，也就是判断$p$到线段端点是否同向。

1	bool OnSegment(Point st,Point ed,Point p) {return dcmp(Cross(st-p,ed-p))==0&&dcmp(Dot(st-p,ed-p))<0;}

判断线段是否相交
有两种线段相交的方式。

一种是规范相交，任意三点不共线，如上图的第一、二种情况。
判断这种情况的方法是：
判断A、B点是否在线段$CD$两侧，即计算叉积时异号，同理也需要判断C、D点是否在线段$AB$两侧。

1	bool Segment_Intersection(Point a1,Point a2,Point b1,Point b2) {return dcmp(Cross(a2-a1,b1-a1))dcmp(Cross(a2-a1,b2-a1))<0&&dcmp(Cross(b2-b1,a1-b1))dcmp(Cross(b2-b1,a2-b1))<0;}

然后考虑第三种情况，也就是非规范相交，有至少三点共线。
这情况发生时有一个点在其它线段上，判断一下即可。

1	bool _Segment_Intersection(Point a1,Point a2,Point b1,Point b2) {return Segment_Intersection(a1,a2,b1,b2)\|\|OnSegment(a1,a2,b1)\|\|OnSegment(a1,a2,b2)\|\|OnSegment(a1,b1,b2)\|\|OnSegment(a2,b1,b2);}

计算直线交点
需要保证相交，否则会GG。
设直线的参数方程为：$P+t\vec v,Q+t\vec w$。
设交点为$P+t_1\vec v=Q+t_2\vec w$。
列出方程组：

$\begin{cases}P_x+t_1\vec v_x=Q_x+t_2\vec w_x \\ P_y+t_1\vec v_y=Q_y+t_2\vec w_y\end{cases}$

解得：

$\begin{cases}t_1=\frac{\vec w\times\vec u}{\vec v\times\vec w} \\ t_2=\frac{\vec v\times\vec u}{\vec v\times\vec w} \\ \vec u=P-Q\end{cases}$

1	Point GetLineIntersection(Point P,Vector v,Point Q,Vector w) {return P+v*(Cross(P-Q,w)/Cross(v,w));}

点到直线距离
叉积除以长度即可得到高度。

1	double DistanceToLine(Point p,Point a,Point b) {Vector v1=b-a,v2=p-a;return fabs(Cross(v1,v2))/v1.length();}

点到线段距离
判断一下是到两个端点更近，还是到直线更近。

double DistanceToSegment(Point p,Point a,Point b) {
	if(a==b)return (p-a).length();
	Vector v1=b-a,v2=p-a,v3=p-b;
	if(dcmp(Dot(v1,v2))<0)return v2.length();
	else if(dcmp(Dot(v1,v3))>0)return v3.length();
	else return DistanceToLine(p,a,b);
}

多边形面积
三角剖分求面积。

double Area(int n,Point* P) {
	double ans=0;
	for(int i=2; i<n; i++)ans+=Area(P[1],P[i],P[i+1]);
	return ans/2;
}