Problem 2: Convex Hull

Problem Statement: Given a set of 2D points, compute the convex hull using Graham's scan algorithm.

Input

The first line contains an integer n, the number of points. Each of the next n lines contains two integers x and y.

Output

Print the vertices of the convex hull in counterclockwise order starting from the vertex with the lowest y-coordinate.

Examples


Input:
6
0 0
1 1
2 2
0 2
2 0
1 -1

Output:
1 -1\n2 0\n2 2\n0 2\n0 0

Solution in C++


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

Point pivot;

int orientation(const Point &a, const Point &b, const Point &c) {
    int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
    if(val == 0) return 0;
    return (val > 0) ? 1 : 2;
}

bool compare(Point a, Point b) {
    int o = orientation(pivot, a, b);
    if(o == 0) {
        return ( (pivot.x - a.x)*(pivot.x - a.x) + (pivot.y - a.y)*(pivot.y - a.y)) <
            ( (pivot.x - b.x)*(pivot.x - b.x) + (pivot.y - b.y)*(pivot.y - b.y));
    }
    return o == 2;
}

int main(){
    int n;
    cin >> n;
    vector<Point> pts(n);
    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }
    int minY = pts[0].y, id = 0;
    for (int i = 1; i < n; i++) {
        if(pts[i].y < minY || (pts[i].y == minY && pts[i].x < pts[id].x)){
            minY = pts[i].y;
            id = i;
        }
    }
    swap(pts[0], pts[id]);
    pivot = pts[0];
    sort(pts.begin() + 1, pts.end(), compare);
    vector<Point> hull;
    hull.push_back(pts[0]);
    hull.push_back(pts[1]);
    for (int i = 2; i < n; i++) {
        while(hull.size() > 1 && orientation(hull[hull.size()-2], hull[hull.size()-1], pts[i]) != 2){
            hull.pop_back();
        }
        hull.push_back(pts[i]);
    }
    for(auto p : hull) {
        cout << p.x << " " << p.y << "\n";
    }
    return 0;
}