#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
    double x;
    double y;

    bool operator!=(const Point &other) {
        return x != other.x || y != other.y;
    }
};

double orientation(const Point &A, const Point &B, const Point &C) 
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

double distance(const Point &A, const Point &B) 
{
    double dx = B.x - A.x;
    double dy = B.y - A.y;

    return dx * dx + dy * dy;
}

void print(const Point &A) 
{
    std::cout << "Point[" << A.x << ", " << A.y << "]" << std::endl;
}

std::vector<Point> jarvis(std::vector<Point> &points) 
{
    Point start = *min_element(points.begin(), points.end(), 
            [](const Point &A, const Point &B) {
                if (A.y == B.y) {
                    return A.x < B.x;
                }
                return A.y < B.y;
            });

    std::vector<Point> CH;

    Point current = start;
    Point candidate = current;
    do {
        for (Point next : points) {
            double o = orientation(current, candidate, next);
            if (o < 0 || (o == 0 && distance(current, candidate) <
                                    distance(current, next))) {
                candidate = next;
            }
        }
        CH.push_back(candidate);
        current = candidate;
    } while (start != current);

    return CH;
}

int main(int argc, const char *argv[])
{
    std::vector<Point> points = {
        {0, 0},
        {1, 1},
        {2, 1},
        {4, 1},
        {2, 3},
        {3, 3},
        {4, 4},
        {1, 4}
    };

    std::vector<Point> CH = jarvis(points);

    for (Point point : CH) {
        print(point);
    }

    return 0;
}