极角排序

简单讲一下极角排序。

我们对于极角排序，就是以x轴为始边，然后到当前点所在的终边，以原点为顶点所形成的角来排序。第二关键字按照到原点的距离。

tan2极角排序

我们把坐标放入 $tan2(y,x) $ 就可以得到极角了。返回的范围是 $[-\pi,\pi]$

其中c是我们想要以其为中心进行极角排序的点，下同。

inline bool cmp(point x,point y){
	db ax=tan2(x.y-c.y,x.x-c.x),ay=tan2(y.y-c.y,y.x-c.x);
	if(sgn(ax-ay)==0) return x.x<y.x;
	return ax<ay;
}

叉积极角排序

由于我们知道叉积可以判断两向量的顺逆时针的位置关系，所以可以用于极角排序。

其中 $a$ 与 $b$ 的叉积若小于0，那么 $a$ 一定在 $b$ 的顺时针方向(右边)。

inline bool cmp(point x,point y){
	//这里是叉积
	db ax=(x-c)*(y-c);
	if(sgn(ax)==0) return dist(x,c)<distA(y,c);
	return ax>0;
}

然后我们不难发现两者的区别，用tan2需要进行的运算次数少，所以相对快。而叉积拥有更加优秀的精度。视情况选择。