c++ - 「競技プログラミング1」の凸包コード

Question

Steven Halim と Felix Halim の著書Competitive Programmingの「凸包」アルゴリズムを理解しようとしています。「凸包」問題は、平面内のn 個の点の集合Pが与えられたときに、他のすべての点を含む凸多角形の頂点を形成するサブセットCH ( P ) を見つけることです。彼らのアプローチの概要を示す画像は次のとおりです。

彼らのアルゴリズムは、「ピボット」、つまりPの一番下と一番右のポイントに対する角度に基づいてポイントをソートすることから始まります。

それらの機能を理解するのにいくつかの問題がありangle_compます—それが何をし、その目的は何ですか。誰かがそれを理解するのを手伝ってくれますか?

typedef struct {
    double x, y ;
} point;

point pivot;

// A function to compute the distance between two points:
double dist2 (point a, point b) 
{
    double dx = a.x - b.x ;
    double dy = a.y - b.y ;
    return sqrt (dx *dx + dy * dy) ;
}

// A function to compare the angles of two points with respect to the pivot:
bool angle_comp (point a, point b)
{
    if (fabs(area2(pivot, a, b) - 0) < 10e-9)
        return dist2(pivot, a) < dist2(pivot, b);

    int d1x = a.x - pivot.x, d1y = a.y - pivot.y;
    int d2x = b.x - pivot.x, d2y = b.y - pivot.y; 
    return (atan2((double) d1y, (double) d1x)
               - atan2 ((double) d2y, (double)d2x))
             < 0;
}