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

struct Point {
    int x;
    int y;
};

Point start;

int distance(Point first, Point second) {
    return (first.x - second.x) * (first.x - second.x) +
           (first.y - second.y) * (first.y - second.y);
}

int orientation(Point around, Point first, Point second) {
    int value = (first.y - around.y) * (second.x - first.x) -
                (first.x - around.x) * (second.y - first.y);
    if (value == 0) return 0;
    return (value > 0) ? 1 : 2;
}

bool compare(const Point first, const Point second) {
    int o = orientation(start, first, second);
    if (o == 0) {
        return (distance(start, second) >= distance(start, first)) ? 1 : 0;
    }
    return (o == 2) ? 1 : 0;
}

Point nextToTop(std::stack<Point>& S) {
    Point temp = S.top();
    S.pop();
    Point result = S.top();
    S.push(temp);
    return result;
}

std::stack<Point> convexHull(std::vector<Point> points) {
    int y_min = points[0].y;
    int min = 0;
    for (int i = 1; i < points.size(); i++) {
        if ((points[i].y < y_min) || (y_min == points[i].y && points[i].x < points[min].x)) {
            y_min = points[i].y;
            min = i;
        }
    }
    std::swap(points[0], points[min]);
    start = points[0];
    std::sort(points.begin() + 1, points.end(),
              [](auto first_point, auto second_point) {
                   return compare(first_point, second_point);
              });
    std::stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);
    for (int i = 3; i < points.size(); i++) {
        while (orientation(nextToTop(S), S.top(), points[i]) != 2) {
            S.pop();
        }
        S.push(points[i]);
    }
    return S;
}

int main() {
    std::vector<Point> p = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },
            { 1, 2 }, { 3, 1 }, { 3, 3 } };
    auto S = convexHull(p);
    while (!S.empty()) {
        Point p = S.top();
        std::cout << p.x << ' ' << p.y << '\n';
        S.pop();
    }
}