#include<vector>
#include<algorithm>
#include<tuple>
#include<cmath>


struct Vector2D {
    double x;
    double y;
    
    Vector2D operator-(Vector2D r) {
        return {x - r.x, y - r.y};
    }
    double operator*(Vector2D r) {
        return x * r.x + y * r.y;
    }
    Vector2D rotate90() {  // Rotate 90 degrees counter-clockwise
        return {-y, x};
    }
    double manhattan_length() {
        return abs(x) + abs(y);
    }
    bool operator==(Vector2D r) {
        return x == r.x && y == r.y;
    }
    bool operator!=(Vector2D r) {
        return x != r.x || y != r.y;
    }
};


std::vector<Vector2D> graham_scan(std::vector<Vector2D> points) {
    Vector2D first_point = *std::min_element(points.begin(), points.end(), [](Vector2D &left, Vector2D &right) {
        return std::make_tuple(left.y, left.x) < std::make_tuple(right.y, right.x);
    });  // Find the lowest and leftmost point
    
    std::sort(points.begin(), points.end(), [&](Vector2D &left, Vector2D &right) {
        if(left == first_point) {
            return right != first_point;
        } else if (right == first_point) {
            return false;
        }
        double dir = (left-first_point).rotate90() * (right-first_point);
        if(dir == 0) {  // If the points are on a line with first point, sort by distance (manhattan is equivalent here)
            return (left-first_point).manhattan_length() < (right-first_point).manhattan_length();
        }
        return dir > 0;
        // Alternative approach, closer to common algorithm formulation but inferior:
        // return atan2(left.y - first_point.y, left.x - first_point.x) < atan2(right.y - first_point.y, right.x - first_point.x);
    });  // Sort the points by angle to the chosen first point
    
    std::vector<Vector2D> result;
    for(auto pt : points) {
        // For as long as the last 3 points cause the hull to be non-convex, discard the middle one
        while (result.size() >= 2 &&
               (result[result.size()-1] - result[result.size()-2]).rotate90() * (pt - result[result.size()-1]) <= 0) {
            result.pop_back();
        }
        result.push_back(pt);
    }
    return result;
}


int main() {
    int n;
    std::vector<Vector2D> pts = {
        {1, 1},
        {3, 2},
        {6, 1},
        {4, 1},
        {5, 1},
        {2, 4},
        {3, 7}
    };
    std::vector<Vector2D> hull = graham_scan(pts);
    return 0;
}