Note: This article is available in Chinese only. 本文暂无英文版本。
View original
20190211update:工作的时候看同事ocr的代码，发现有一段就是极角排序orz…所以说算法还是有用的…
先介绍几种极角排序：
1.利用叉积的正负来作cmp.(即是按逆时针排序).此题就是用这种方法
1 bool cmp(const point &a, const point &b)//逆时针排序
2 {
3 point origin;
4 origin.x = origin.y = 0;
5 return cross(origin,b,origin,a) < 0;
6 }2.利用complex的内建函数。
1 #include
2 #define x real()
3 #define y imag()
4 #include
5 using namespace std;
6
7 bool cmp(const Point& p1, const Point& p2)
8 {
9 return arg(p1) < arg(p2);
10 }3.利用arctan计算极角大小。（范围『-180，180』）
1 bool cmp(const Point& p1, const Point& p2)
2 {
3 return atan2(p1.y, p1.x) < atan2(p2.y, p2.x);
4 }4.利用象限加上极角，叉积。
1 bool cmp(const point &a, const point &b)//先按象限排序，再按极角排序，再按远近排序
2 {
3 if (a.y == 0 && b.y == 0 && a.x*b.x <= 0)return a.x>b.x;
4 if (a.y == 0 && a.x >= 0 && b.y != 0)return true;
5 if (b.y == 0 && b.x >= 0 && a.y != 0)return false;
6 if (b.y*a.y <= 0)return a.y>b.y;
7 point one;
8 one.y = one.x = 0;
9 return cross(one,a,one,b) > 0 || (cross(one,a,one,b) == 0 && a.x < b.x);
10}