Convex Hull

/* Convex Hull */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

struct point
{
    int x, y;
};

stack<point> S;
point p0;

int orientation(point p0, point p1, point p2)
{
    int t = (p2.y - p1.y) * (p1.x - p0.x) - (p1.y - p0.y) * (p2.x - p1.x);
    return t;
}

bool comp1(point p1, point p2)
{
    int o = orientation(p0, p1, p2);
    if(o > 0) return true;
    else if(o < 0) return false;
    else {
        int d1 = (p1.x - p0.x) * (p1.x - p0. x) + (p1.y - p0.y) * (p1.y - p0.y);
        int d2 = (p2.x - p0.x) * (p2.x - p0. x) + (p2.y - p0.y) * (p2.y - p0.y);
        if(d1 < d2) return true;
        else return false;
    }
}

bool comp2(point p1, point p2)
{
    if(p1.y < p2.y) return true;
    else if(p1.y > p2.y) return false;
    else {
        if(p1.x < p2.x) return true;
        else return false;
    }
}

point nextTop(stack<point> S)
{
    S.pop();
    return S.top();
}

void convexHull(point p[], int n)
{
    sort(p, p+n, comp2);
    p0 = p[0];
    sort(p, p+n, comp1);
    S.push(p[0]);
    S.push(p[1]);
    S.push(p[2]);
    for(int i=3; i<n; i++){
        while(orientation(nextTop(S), S.top(), p[i]) < 0) S.pop();
        S.push(p[i]);
    }
    while(!S.empty()){
        cout << S.top().x << " " << S.top().y << endl;
        S.pop();
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    point p[n];
    for(int i=0; i<n; i++) scanf("%d %d", &p[i].x, &p[i].y);
    convexHull(p, n);
}