//ALGO2 IS1 213B LAB10
//MACIEJ DOMINIAK
//dm44308@zut.edu.pl
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <stdio.h>
using namespace std;
class Point {
public:
    double x;
    double y;
    int index;

    void printPoint(int i) {
        cout << index << " Point(" << x << "," << y << ")" << endl;
    }
};
class Node {
public:
    Point* point;
    Node* next;
};
class List {
public:
    Node* head;
    int size;
    List() {
        head = NULL;
        size = 0;
    }
    void addBack(Point* point) {
        Node* temp = new Node;
        temp->point = point;
        temp->next = NULL;
        if (head == NULL) {
            head = temp;
            return;
        }
        else {
            Node* last = head;
            while (last->next)last = last->next;
            last->next = temp;
            size++;
        }

    }
    void deleteSec() {
        Node* current = head;
        Node* curr_succ = current->next;
        Node* succ_succ = curr_succ->next;
        while (succ_succ->next != NULL) {
            current = current->next;
            curr_succ = curr_succ->next;
            succ_succ = succ_succ->next;
        }
        current->next = succ_succ;
        size--;
    }
    Node* getTopNodes() {
        Node* current = head;
        while (current->next->next->next != NULL)
            current = current->next;
        return current;
    }
    void printPoints() {
        Node* current = head;
        while (current != NULL) {
            cout << current->point->index << " Point(" << current->point->x << "," << current->point->y << ")" << endl;
            current = current->next;
        }
    }
};

class Graham {
public:

    int n;
    Point* points;
    Graham(Point points[], int n) {
        this->points = new Point[n];
        this->n = n;
        for (int i = 0; i < n; i++) {
            this->points[i] = points[i];
        }
    }

    int pointComparator(Point* point1, Point* point2, Point* point3) {
        double cross_prod = (point1->y - point3->y) * (point2->x - point3->x) - (point2->y - point3->y) * (point1->x - point3->x);
        if (cross_prod > 0.0)
            return 1;
        if (cross_prod < 0.0)
            return -1;
        return 0;
    }

    void findSetMin() {
        int temp = 0;
        for (int i = 1; i < n; i++) {
            if (points[temp].y >= points[i].y) {
                if (points[temp].y == points[i].y) {
                    if (points[temp].x > points[i].x) {
                        temp = i;
                    }
                }
                else {
                    temp = i;
                }
            }
        }
        swap(points[0], points[temp]);
    }
    void printPoints() {
        for (int i = 0; i < n; i++)
            points[i].printPoint(i);
    }

    void sortPoints() {
        for (int j = 0; j < n - 1; j++) {
            for (int i = 1; i < n - j - 1; i++)
                if (pointComparator(&points[i], &points[i + 1], &points[0]) > 0) {
                    swap(points[i], points[i + 1]);
                }
            cout << j << endl;
        }
    }
    int pointComparatorGraham(Point* point1, Point* point2) {
        double cross_prod = (point1->y * point2->x) - (point2->y * point1->x);
        if (cross_prod > 0.0)
            return 1;
        if (cross_prod < 0.0)
            return -1;
        return 0;
    }
    Point* pointSubstract(Point* point1, Point* point2) {
        Point* temp = new Point();
        temp->x = point2->x - point1->x;
        temp->y = point2->y - point1->y;
        temp->index = -1;
        return temp;
    }
    void merge(int l, int m, int r)
    {
        int i, j, k;
        int n1 = m - l + 1;
        int n2 = r - m;

        Point* tempL = new Point[n1];
        Point* tempR = new Point[n2];

        for (i = 0; i < n1; i++)
            tempL[i] = points[l + i];
        for (j = 0; j < n2; j++)
            tempR[j] = points[m + 1 + j];

        i = 0;
        j = 0;
        k = l;
        while (i < n1 && j < n2)
        {
            if(pointComparator(&tempL[i],&tempR[j],&points[0])<0)
            {
                points[k] = tempL[i];
                i++;
            }
            else
            {
                points[k] = tempR[j];
                j++;
            }
            k++;
        }

        while (i < n1)
        {
            points[k] = tempL[i];
            i++;
            k++;
        }

        while (j < n2)
        {
            points[k] = tempR[j];
            j++;
            k++;
        }
    }

    void mergeSort(int l, int r)
    {
        if (l < r)
        {
            int m = l + (r - l) / 2;

            mergeSort(l, m);
            mergeSort( m + 1, r);

            merge(l, m, r);
        }
    }
    List* grahamScan() {
        findSetMin();
        //sortPoints();
        mergeSort(1, n - 1);
        List* convex_hull = new List();
        convex_hull->addBack(&points[0]);
        convex_hull->addBack(&points[1]);
        convex_hull->addBack(&points[2]);
        for (int i = 3; i < n; i++) {
            Node* lastnodes = convex_hull->getTopNodes();
            Point* result1 = pointSubstract(lastnodes->next->point, lastnodes->next->next->point);
            Point* result2 = pointSubstract(lastnodes->point, lastnodes->next->point);
            while (pointComparatorGraham(result1, result2) < 0) {
                convex_hull->deleteSec();
                lastnodes = convex_hull->getTopNodes();
                result1 = pointSubstract(lastnodes->next->point, lastnodes->next->next->point);
                result2 = pointSubstract(lastnodes->point, lastnodes->next->point);
            }
            convex_hull->addBack(&points[i]);

        }
        return convex_hull;
    }
};
int main()
{
    ifstream my_file;
    my_file.open("points5.txt");
    int n;
    Point* points;
    if (my_file.good()) {
        my_file >> n;
        points = new Point[n];
        for (int i = 0; i < n; i++) {
            my_file >> points[i].x;
            my_file >> points[i].y;
            points[i].index = i;
        }
    }
    else {
        cout << endl << "Could not open the file, ending program..." << endl;
        return 0;
    }
    my_file.close();
    Graham* graham = new Graham(points, n);
    graham->findSetMin();
    List* convex_hull = graham->grahamScan();
    cout << endl;
    cout << endl;
    convex_hull->printPoints();
    return 0;
}