#include <iterator>
#include <stdint.h>
#include <limits>
#include <vector>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <iterator>
#include <sstream>
#include "iostream"

using namespace std;

struct Point
{
    int x, y;
};

void print_arrat(vector<Point> points) {
    for (int i = 0; i < points.size(); ++i) {
        Point current = points.at(i);
        cout << current.x << " " << current.y << endl;
    }
}

float cotan(Point p1, Point p2) {
    return (p2.x - p1.x) / (p2.y - p1.y);
}

int dist(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) +
          (p1.y - p2.y)*(p1.y - p2.y);
}

int comparePoints(Point p1, Point p2, Point reference) {
    if (p1.y == reference.y && p2.y == reference.y) {
        return (dist(p1, reference) < dist(p2, reference)) ? -1 : 1;
    } else if (p1.y == reference.y) {
        return 1;
    } else if (p2.y == reference.y) {
        return -1;
    } else {
        float cotan_p1 = cotan(reference, p1);
        float cotan_p2 = cotan(reference, p2);
        if (cotan_p1 == cotan_p2) {
            return 0;
        }
        return (cotan_p1 < cotan_p2) ? -1 : 1;
    }
}

class PointSorter{
    Point point_;
public:
    PointSorter(Point point){ point_ = point; }
    int operator()(Point p1, Point p2) const {
        return comparePoints(p1 , p2 , point_);
    }
};

void find_convex_hull(vector<Point> points) {
    Point lowest = points.at(0);
    int index = 0;
    // TODO refactor
    for (int i = 1; i < points.size(); ++i) {
        Point current = points.at(i);
        if (current.y < lowest.y) {
            lowest = current;
            index = i;
        } else if (current.y == lowest.y && current.x < lowest.x) {
            index = i;
            lowest = current;
        }
    }
    // Swap lowest point to the beginning of the list
    Point tmp = points.at(0);
    points.at(0) = lowest;
    points.at(index) = tmp;
    print_arrat(points);
    cout << endl;
    sort(++points.begin(), points.end(), PointSorter(lowest));
    print_arrat(points);
}

int main(int argc, char *argv[]) {
    Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                      {0, 0}, {1, 2}, {3, 1}, {3, 3}, {-2, 2}};
    vector<Point> bulb(points, points + sizeof points / sizeof points[0]);
    find_convex_hull(bulb);
}