Graham Scan algorithm

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>

using namespace std;

typedef struct Point_
{
    double x;
    double y;
} Point;

double polar_angle(Point a, Point b)
{
    return atan2(a.y - b.y, a.x - b.x);
}

double ccw(Point a, Point b, Point c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

Point convex_hull_find_p0(vector<Point> &points)
{
    Point p0 = points[0];

    for (Point &point : points)
    {
        if (p0.y < point.y)
            p0 = point;
        else if (p0.y == point.y && p0.x > point.x)
            p0 = point;
    }

    return p0;
}

vector<int> convex_hull(vector<Point> &points)
{
    vector<int> result;

    Point p0 = convex_hull_find_p0(points);
    vector<int> points_idxs(points.size());
    iota(points_idxs.begin(), points_idxs.end(), 0);

    sort(points_idxs.begin(),
         points_idxs.end(),
         [&](int &a, int &b)
         { return polar_angle(p0, points[a]) < polar_angle(p0, points[b]); });

    for (int &index : points_idxs)
    {
        while (result.size() > 1 && ccw(points[result[result.size() - 2]], points[result.back()], points[index]) <= 0)
            result.pop_back();

        result.push_back(index);
    }

    return result;
}

int main()
{
    vector<Point> points = {{35.850, 26.850},
                            {52.875, 10.875},
                            {72.750, 70.650},
                            {21.900, 28.650},
                            {53.850, 67.125},
                            {50.025, 22.425},
                            {2.625, 67.050},
                            {41.025, 48.300},
                            {23.700, 2.625},
                            {14.250, 63.150},
                            {16.500, 7.950},
                            {19.800, 48.600},
                            {33.450, 60.375},
                            {66.750, 54.675},
                            {0.450, 7.575},
                            {6.300, 71.550},
                            {69.675, 40.575},
                            {1.575, 55.875},
                            {69.300, 5.400},
                            {7.275, 38.400},
                            {73.950, 21.750},
                            {49.125, 43.050},
                            {2.325, 3.900}};

    vector<int> result = convex_hull(points);
    sort(result.begin(), result.end());

    cout << "Number of points of convex hull: " << result.size() << endl;
    
    cout << "Points: {";
    for (int &index : result)
        cout << index << ", ";
    cout << "}" << endl;
    
}