Convex Hull

 #include <iostream>

#include <stack>

using namespace std;

struct Point

{

    int x, y;

};

// Utility function to find the next to top element in the stack

Point nextToTop(stack<Point> &S)

{

    Point p = S.top();

    S.pop();

    Point res = S.top();

    S.push(p);

    return res;

}

// Utility function to swap two points

void swap(Point &p1, Point &p2)

{

    Point temp = p1;

    p1 = p2;

    p2 = temp;

}

// Utility function to return the square of the distance between p1 and p2

int distSq(Point p1, Point p2)

{

    return (p1.x - p2.x) * (p1.x - p2.x) +

           (p1.y - p2.y) * (p1.y - p2.y);

}

// To find orientation of the ordered triplet (p, q, r).

// The function returns the following values:

// 0 -> p, q and r are collinear

// 1 -> Clockwise

// 2 -> Counterclockwise

int orientation(Point p, Point q, Point r)

{

    int val = (q.y - p.y) * (r.x - q.x) -

              (q.x - p.x) * (r.y - q.y);

    if (val == 0)

        return 0;             // collinear

    return (val > 0) ? 1 : 2; // clock or counterclock wise

}

// Function to perform a custom sort of points according to their polar angle with p0

void customSort(Point points[], int n, Point p0)

{

    for (int i = 1; i < n - 1; ++i)

    {

        for (int j = 1; j < n - i - 1; ++j)

        {

            if (orientation(p0, points[j], points[j + 1]) == 1 ||

                (orientation(p0, points[j], points[j + 1]) == 0 &&

                 distSq(p0, points[j + 1]) < distSq(p0, points[j])))

            {

                swap(points[j], points[j + 1]);

            }

        }

    }

}

// Function to find the convex hull of a set of n points

void convexHull(Point points[], int n)

{

    // Find the bottom-most point

    int ymin = points[0].y, min = 0;

    for (int i = 1; i < n; i++)

    {

        int y = points[i].y;

        if ((y < ymin) || (ymin == y && points[i].x < points[min].x))

            ymin = points[i].y, min = i;

    }

    // Place the bottom-most point at the first position

    swap(points[0], points[min]);

    // Set p0 as the first point

    Point p0 = points[0];

    // Sort n-1 points with respect to the first point using custom sort

    customSort(points, n, p0);

    // Create an empty stack and push first three points to it

    stack<Point> S;

    S.push(points[0]);

    S.push(points[1]);

    S.push(points[2]);

    // Process remaining n-3 points

    for (int i = 3; i < n; i++)

    {

        while (orientation(nextToTop(S), S.top(), points[i]) != 2)

            S.pop();

        S.push(points[i]);

    }

    // Print the contents of stack

    cout << "Convex Hull points:\n";

    while (!S.empty())

    {

        Point p = S.top();

        cout << "(" << p.x << ", " << p.y << ")\n";

        S.pop();

    }

}

int main()

{

    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};

    int n = sizeof(points) / sizeof(points[0]);

    convexHull(points, n);

    return 0;

}