algorithm - 凸包排序步骤

Question

我正在阅读格雷厄姆扫描算法以从 CLRS 中找到凸包。Convex hull在CLRS中给出的算法是::

我无法理解这一行(算法的第 2 步):

If two or more points have the same polar angle relative to p0, all but the farthest such point are convex combinations of p0 and the farthest point, and so we remove them entirely from consideration.

1. 这是什么意思？多个点相对于 Po 的极角相同怎么办？

还可以说，我做了一个结构

struct points
{
    int x, y;
} P[10000];

1. 我应该如何使用 C++ STL 库实现排序步骤？我的意思是，我应该如何在 sort(P+1, P+N, comparator) 中定义 comparator 函数？

Answer 1

What does this mean,what should i do if more than one points have the same polar angle with respect to Po?

假设 P₀ 是 (0,0)，P₁ 是 (1,1) P₂ 是 (2,2)。现在 P₁ 和 P₂ 相对于 P₀ 有相同的角度，在这种情况下你丢弃 P₁ .如果 P₀ 和 P₂ 之间有更多点具有相同的角度，则丢弃除 P₂ 之外的所有(当然还有 P₀)。

How should i implement the sorting step using C++ STL (sort function in Algorithm ) Library?Especially i mean sort(P+1,P+N,comparator). How should I define the comparator function?

不太熟悉 C++ (STL)，但请检查它是否有您可以使用的 atan2 函数。另见:Find angle between two points, respective to horizontal axis?和 How to calculate the angle between a line and the horizontal axis?