Graham's Scan (Andrew v.)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

struct punct {
    double x, y;
    void print_punct() {
        cout << '(' << x << ", " << y << ')';
    }
    bool operator==(const punct& B) {
        if (abs(x - B.x) < 0.000001 && abs(y - B.y) < 0.000001)
            return true;
        return false;
    }
};

bool cmp(punct& A, punct& B) {
    if (A.x < B.x)
        return true;
    if (A.x > B.x)
        return false;
    if (A.y < B.y)
        return true;
    return false;
}

bool viraj(vector <punct>& stiva) {
    int n = stiva.size();
    double x1 = stiva[n - 3].x, y1 = stiva[n - 3].y;
    double x2 = stiva[n - 2].x, y2 = stiva[n - 2].y;
    double x3 = stiva[n - 1].x, y3 = stiva[n - 1].y;
    double det = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
    if (det > 0)
        return true;
    return false;
}

int main() {
    vector <punct> A(4);
    double a, b;
    for (int i = 0; i < 4; i++) {
        cin >> a >> b;
        A[i].x = a;
        A[i].y = b;
    }

    sort(A.begin(), A.end(), cmp);
    punct st = A[0], dr = A[3];
    vector <punct> stiva;
    stiva.push_back(A[0]);
    stiva.push_back(A[1]);

    for (int i = 2; i < 4; i++) {
        stiva.push_back(A[i]);
        while (stiva.size() > 2 && !viraj(stiva)) {
            stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
            stiva.pop_back();
        }
    }

    vector <punct> sol = stiva;
    stiva.clear();
    stiva.push_back(A[3]);
    stiva.push_back(A[2]);
    for (int i = 1; i >= 0; i--) {
        stiva.push_back(A[i]);
        while (stiva.size() > 2 && !viraj(stiva)) {
            stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
            stiva.pop_back();
        }
    }

    for (int i = 1; i < stiva.size() - 1; i++)
            sol.push_back(stiva[i]);

    cout << "Acoperirea convexa este: ";
    for (auto &&el: sol) {
        el.print_punct();
        cout << ", ";
    }


    cout << "\nI = {\n";
    if (sol.size() == 4) {
        sol[0].print_punct();
        cout << ", ";
        sol[2].print_punct();
        cout << "}\nJ = {\n";
        sol[1].print_punct();
        cout << ", ";
        sol[3].print_punct();
        cout << "}\n";
    }
    else {
        for (auto &&el: sol) {
            el.print_punct();
            cout << ", ";
        }
        cout << "}\nJ = {\n";
        bool found;
        for (int i = 0; i < 4; i++){
            found = false;
            for (int j = 0; j < sol.size(); j++) {
                if (A[i] == sol[j]) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                A[i].print_punct();
                cout << ", ";
            }
        }
        cout << "}";
    }

    return 0;
}