通过一个简单的排序算法,从不同角度解决问题。
今天第一次接触到几何类的问题,看到了一个极角排序,感觉很有用处。
我们平常所使用的坐标系都是直角坐标系,而极角排序是在极坐标系下进行的。 这里首先要选取一个点,然后其它点根据与参考点的连线与x轴所成的夹角的大小进行排序的。 这里我们可以简单理解为绕着一个点逆时针转圈访问。
盗一下别人家的图来用一下。。。
对于计较排序来说,最重要的还是cmp函数的书写,这里有一下几种书写方式:
1、 利用叉积的正负来作 cmp 。
2、 用 complex 的内建函数,算出极角大小。这个函数没有用过。
3、 用 arctan 计算极角大小。注意角的大小范围是(-180°, +180°]。弧度表示。这里用 arctan2 函数应该是为了提高精度。
4、 先判断象限,再用外积判断顺序,最后根据长度排序。
5、 先判断象限,再用外积判断顺序。适用于每个点的极角都不相同。
最后别忘了几个重要的东西,根据自己的需要修改吧。
补充一下在题目中遇到的极角排序的 cmp 函数的写法: