#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

#include <stack>
#include <queue>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

class Point
{
    int id;
    double x, y;

public:
    Point(int, double, double);

    int getId();
    double getX();
    double getY();

    void display();

    double operator*(Point&);
    bool operator>(Point&);
    bool operator<(Point&);

    static int calcAngle(Point*, Point*);
};

class GrahamAlgorithm
{
    vector<Point*> points;
    vector<Point*> results;

    Point createVector(Point*, Point*);
public:
    GrahamAlgorithm(string);
    ~GrahamAlgorithm();

    Point* findMinimium();
    vector<Point*> sort();

    void execute();
    void display();

    bool comparator(Point*, Point*);
};

Point::Point(int id, double x, double y)
{
    this->id = id;
    this->x = x;
    this->y = y;
}

int Point::getId()
{
    return this->id;
}

double Point::getX()
{
    return this->x;
}

double Point::getY()
{
    return this->y;
}

void Point::display()
{
    cout << id << " " << x << " " << y << endl;
}

double Point::operator*(Point& b)
{
    return this->y * b.x - b.y * this->x;
}

bool Point::operator>(Point& b)
{
    return *this * b >= 0;
}

bool Point::operator<(Point& b)
{
    return *this * b < 0;
}

int Point::calcAngle(Point* point1, Point* point2)
{
    double x1 = point1->getX();
    double x2 = point2->getX();

    double y1 = point1->getY();
    double y2 = point2->getY();

    double a = fabs(x2 - x1);
    double b = y2 - y1;

    int angle = atan(b / a) * 180 / M_PI;

    return x2 < x1 ? 180 - angle : angle;
}

GrahamAlgorithm::GrahamAlgorithm(string filePath)
{
    fstream file(filePath);

    if (!file.good()) {
        throw "ERROR: Cannot read file!";
    }

    int n;
    file >> n;

    for (int i = 0; i < n; i++) {
        double x, y;

        file >> x;
        file >> y;

        this->points.push_back(new Point(i, x, y));
    }

    file.close();
}

GrahamAlgorithm::~GrahamAlgorithm()
{
    for (auto & it : this->points) {
        delete it;
    }
}

Point GrahamAlgorithm::createVector(Point* a, Point* b)
{
    Point vector(0, b->getX() - a->getX(), b->getY() - a->getY());
    return vector;
}

Point* GrahamAlgorithm::findMinimium()
{
    Point* minimum = points[0];

    for (auto & point : points) {
        if (*minimum > *point) {
            minimum = point;
        }
    }

    return minimum;
}

// znowu heap sort, jakby ktoś pytał
vector<Point*> GrahamAlgorithm::sort()
{
    vector<Point*> heap;

    Point* minimal = findMinimium();
    Point normal = *minimal;

    int heapSize = 0;
    for (auto & point : points) {
        if (point == minimal) {
            continue;
        }

        heap.push_back(point);
        heapSize++;

        int index = heapSize - 1;
        int parentIndex = (index - 1) / 2;

        while (index > 0) {
            Point* current = heap[index];
            Point* parent = heap[parentIndex];

            if (Point::calcAngle(minimal, current) < Point::calcAngle(minimal, parent)) {
                Point* temp = heap[index];
                heap[index] = heap[parentIndex];
                heap[parentIndex] = temp;
            } else {
                break;
            }

            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    vector<Point*> sorted;

    while (heapSize > 0) {
        sorted.push_back(heap[0]);

        Point* temp = heap[0];
        heap[0] = heap[heapSize - 1];
        heap[heapSize - 1] = temp;

        heap.erase(heap.end() - 1);
        heapSize--;

        int parent = 0;

        int left = parent * 2 + 1;
        int right = parent * 2 + 2;

        while (parent < heapSize) {
            if (right < heapSize) {
                if (Point::calcAngle(minimal, heap[left]) < Point::calcAngle(minimal, heap[right])) {
                    if (Point::calcAngle(minimal, heap[left]) < Point::calcAngle(minimal, heap[parent])) {
                        temp = heap[parent];
                        heap[parent] = heap[left];
                        heap[left] = temp;

                        parent = left;
                    } else {
                        break;
                    }
                } else {
                    if (Point::calcAngle(minimal, heap[left]) < Point::calcAngle(minimal, heap[parent])) {
                        temp = heap[parent];
                        heap[parent] = heap[right];
                        heap[right] = temp;

                        parent = right;
                    } else {
                        break;
                    }
                }
            } else if (left < heapSize) {
                if (Point::calcAngle(minimal, heap[left]) < Point::calcAngle(minimal, heap[parent])) {
                    temp = heap[parent];
                    heap[parent] = heap[left];
                    heap[left] = temp;

                    parent = left;
                } else {
                    break;
                }
            } else {
                break;
            }

            left = parent * 2 + 1;
            right = parent * 2 + 2;
        }
    }

    return sorted;
}

bool GrahamAlgorithm::comparator(Point* a, Point* b)
{
    int angle = Point::calcAngle(a, b);
    return angle > 0 && angle < 90;
}

void GrahamAlgorithm::execute()
{
    Point* minimal = findMinimium();
    vector<Point*> sortedPoints = sort();

    results.push_back(minimal);
    results.push_back(sortedPoints[0]);

    queue<Point*> line;
    for (int i = 1; i < sortedPoints.size(); i++) {
        line.push(sortedPoints[i]);
    }

    Point* current = line.front();
    line.pop();

    Point* prelast = line.front();
    line.pop();

    Point* last;

    while (!line.empty()) {
        last = line.front();
        line.pop();

        results.push_back(current);

        Point a = createVector(current, prelast);
        Point b = createVector(prelast, last);

        while (b * a < 0) {
            prelast = *(results.end() - 1);
            results.pop_back();

            current = *(results.end() - 1);

            a = createVector(current, prelast);
            b = createVector(prelast, last);
        }

        current = prelast;
        prelast = last;
    }
}

void GrahamAlgorithm::display()
{
    Point* minimum = findMinimium();

    cout << "Points:" << endl;
    for (auto & point : points) {
        point->display();
    }

    cout << endl << "Sorted: " << endl;
    for (auto & it : sort()) {
        it->display();
    }

    cout << endl << "Solution: ";
    for (auto & point : results) {
        cout << point->getId() << " -> ";
    }

    cout << results[0]->getId() << endl
         << "Number of points: " << results.size() << endl << endl;

    Point* a = points[88];
    Point* b = points[5];
    Point* c = points[84];

    Point vecA = createVector(a, b);
    Point vecB = createVector(b, c);

    cout << vecB * vecA << endl << endl;
}

int main()
{
    try {
        GrahamAlgorithm* algorithm = new GrahamAlgorithm("points2.txt");

        clock_t start = clock();
        algorithm->execute();
        clock_t end = clock();
        algorithm->display();

        cout << fixed << "Total time: " << (double) (end - start) / CLOCKS_PER_SEC << endl << endl;
        delete algorithm;
    } catch (string err) {
        cerr << err << endl << endl;
        exit(EXIT_FAILURE);
    }
}