(B)我应该如何使用 C++ STL(算法中的排序函数)库实现排序步骤?特别是我的意思是排序(P+1,P+N,比较器)。我应该如何定义比较器功能?
我建议你避免凌乱的浮点运算。正如同一本书的练习 33.1-3 所指出的,您可以使用叉积简单地按极角排序。这是如何做到的:
struct Point {int x,y;}
int operator^(Point p1, Point p2) {return p1.x*p2.y - p1.y*p2.x;}
Point p0; //set this separately
bool operator<(Point p1, Point p2)
{
p1=p1-p0; p2=p2-p0;
if(p1.y==0&&p1.x>0) return true; //angle of p1 is 0, thus p2>p1
if(p2.y==0&&p2.x>0) return false; //angle of p2 is 0 , thus p1>p2
if(p1.y>0&&p2.y<0) return true; //p1 is between 0 and 180, p2 between 180 and 360
if(p1.y<0&&p2.y>0) return false;
return (p1^p2)>0; //return true if p1 is clockwise from p2
}
(A)这是什么意思,如果多个点相对于Po有相同的极角,我该怎么办?
如果 p0、pi 和 pj 共线,只有离 p0 最远的那个可能是凸包的一部分。因此,我们应该删除其他点。我们可以在 C++ 中做到这一点。首先定义点积,
int operator*(Point p1, Point p2) {return p1.x*p2.x + p1.y*p2.y;}
并将这一行添加到比较器:
if((p1^p2)==0&&p1*p2>0) return p1*p1<p2*p2;
现在在相同角度的情况下,点将按与 p0 的距离排序。现在我们可以使用unique
STL 中的函数根据需要从以下位置删除点vector<Point> P
:
sort(P.begin(),P.end());
P.erase(unique(P.begin(),P.end(),eq),P.end());
在这里,eq
如果点的角度相同,则函数返回 true。
bool eq(Point p1, Point p2)
{
p1=p1-p0; p2=p2-p0;
return ((p1^p2)==0&&p1*p2>0);
}