#include <algorithm>
#include <cassert>
#include <cilk/cilk.h>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 1123456;

struct Point {
    int x, y;
    Point() {}
    Point(int x, int y): x(x), y(y) {}
    Point operator+(const Point& o) const { return Point(x+o.x, y+o.y); }
    Point operator-(const Point& o) const { return Point(x-o.x, y-o.y); }
    int operator%(const Point& o) const {
        return x*o.y - y*o.x;
    }
    bool operator<(const Point& o) const {
        return x != o.x ? x < o.x : y < o.y;
    }
};

typedef Point Vector;
typedef vector<Point> Polygon;

int n;
Polygon point;

inline int ccw(const Point& p, const Point& q, const Point& r) {
    return (q - p) % (r - p);
}

Polygon convex_hull_sequential() {
    Polygon hull(n);
    int k = 0;
    hull[k++] = point[0];
    for (int i = 1; i < n; i++) {
        while (k > 1 && ccw(hull[k-2], hull[k-1], point[i]) >= 0) k--;
        hull[k++] = point[i];
    }
    // for (int i = n-2, lim = k; i >= 0; i--) {
    //     while (k > lim && ccw(hull[k-2], hull[k-1], point[i]) >= 0) k--;
    //     hull[k++] = point[i];
    // }
    // k--;
    hull.resize(k);

    return hull;
}

Polygon convex_hull_parallel(int l, int r) {
    // if size is <= 4, bruteforce solution
    if (r-l < 6) {
        assert(l < r);
        Polygon UH(r-l+1);
        int k = 0;
        UH[k++] = point[l];
        // if (l == 4 and r == 7) printf(":: %d %d\n", point[l].x, point[l].y);
        for (int i = l+1; i <= r; i++) {
            while (k > 1 && ccw(UH[k-2], UH[k-1], point[i]) >= 0) k--;
            UH[k++] = point[i];
            // if (l == 4 and r == 7) printf("%d %d\n", point[i].x, point[i].y);
        }
        // if (l == 4 and r == 7) puts("");
        UH.resize(k);
        return UH;
    }

    // divide
    int m = (l+r)/2;
    Polygon UH1 = convex_hull_parallel(l, m);
    Polygon UH2 = convex_hull_parallel(m+1, r);

    printf("UH1: %d %d\n", l, m);
    for (const Point& p: UH1) printf("%d %d\n", p.x, p.y);

    printf("UH2: %d %d\n", m+1, r);
    for (const Point& p: UH2) printf("%d %d\n", p.x, p.y);

    // conquer
    // TODO: don't create new vector to return
    int s = UH1.size(), t = UH2.size();

    // double binary search to find upper commom tangent
    int l1 = 0, r1 = s-1, l2, r2;
    while (l1 < r1) {
        int m1 = (l1+r1)/2;
        l2 = 0, r2 = t-1;
        while (l2 < r2) {
            int m2 = (l2+r2)/2;
            int abovePred = ccw(UH1[m1], UH2[(m2+t-1)%t], UH2[m2]) >= 0;
            int aboveSucc = ccw(UH1[m1], UH2[(m2+1)%t], UH2[m2]) >= 0;
            if (abovePred and aboveSucc) {
                l2 = r2 = m2;
            } else if (abovePred) {
                l2 = m2+1;
            } else {
                r2 = m2-1;
            }
        }
        int abovePred = ccw(UH2[l2], UH1[m1], UH1[(m1+s-1)%s]) >= 0;
        int aboveSucc = ccw(UH2[l2], UH1[m1], UH1[(m1+1)%s]) >= 0;
        if (abovePred and aboveSucc) {
            l1 = r1 = m1;
        } else if (abovePred) {
            l1 = m1+1;
        } else {
            r1 = m1-1;
        }
    }

    printf("UH1[l1]: %d %d\n", UH1[l1].x, UH1[l1].y);
    printf("UH2[l2]: %d %d\n\n", UH2[l2].x, UH2[l2].y);

    Polygon UH(l1+1+t-l2);
    for (int i = 0; i < l1+1; ++i)
        UH[i] = UH1[i];
    for (int i = 0; i < t-l2; ++i)
        UH[l1+1+i] = UH2[l2+i];

    return UH;
}

int main() {

    srand(time(NULL));

    // get input data
    scanf("%d", &n);
    // n = 256;
    point.resize(n);
    // printf("%d\n", n);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &point[i].x, &point[i].y);
        // point[i] = Point(rand()%2048, rand()%2048);
        // printf("%d %d\n", point[i].x, point[i].y);
    }

    // for (int i = 0; i < n; ++i)
    //     for (int j = i+1; j < n; ++j)
    //         for (int k = j+1; k < n; ++k)
    //             if (ccw(point[i], point[j], point[k]) == 0)
    //                 return printf("Three colinear points: %d %d %d\n", i, j, k), 0;

    // return 0;
    // sort points by x coordinate
    sort(point.begin(), point.end());

    // sequential version of convex hull
    Polygon CHs = convex_hull_sequential();
    puts("Upper Hull (sequential):");
    for (const Point& p: CHs) printf("%d %d\n", p.x, p.y);
    puts("");

    // parallel version of convex hull
    Polygon CHp = convex_hull_parallel(0, n-1);
    puts("Upper Hull (parallel):");
    for (const Point& p: CHp) printf("%d %d\n", p.x, p.y);
    puts("");

    return 0;
}