Cod sursa(job #3333183)

Utilizator stefdani1Danaila Stefan-Alexandru stefdani1 Data 11 ianuarie 2026 18:28:33
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.56 kb
#include <fstream>
#include <iomanip>

using namespace std;

struct Punct {
    long double x, y;
};

long double cross(const Punct &O, const Punct &A, const Punct &B) {
    // (A - O) x (B - O)
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

bool lessPt(const Punct &a, const Punct &b) {
    if (a.x < b.x) return true;
    if (a.x > b.x) return false;
    return (a.y < b.y);
}

bool equalPt(const Punct &a, const Punct &b) {
    return (a.x == b.x && a.y == b.y);
}

// MergeSort fără STL
void mergeSort(Punct *v, Punct *tmp, int st, int dr) {
    if (st >= dr) return;
    int mid = (st + dr) / 2;
    mergeSort(v, tmp, st, mid);
    mergeSort(v, tmp, mid + 1, dr);

    int i = st, j = mid + 1, k = st;
    while (i <= mid && j <= dr) {
        if (lessPt(v[i], v[j])) tmp[k++] = v[i++];
        else tmp[k++] = v[j++];
    }
    while (i <= mid) tmp[k++] = v[i++];
    while (j <= dr) tmp[k++] = v[j++];

    for (int t = st; t <= dr; t++) v[t] = tmp[t];
}

int main() {
    ifstream fin("HULL.in");
    ofstream fout("HULL.out");

    int n;
    fin >> n;

    Punct *p = new Punct[n];
    for (int i = 0; i < n; i++) fin >> p[i].x >> p[i].y;

    // sortare dupa (x, y)
    Punct *tmp = new Punct[n];
    mergeSort(p, tmp, 0, n - 1);
    delete[] tmp;

    // eliminare duplicate (daca exista)
    int m = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || !equalPt(p[i], p[m - 1])) p[m++] = p[i];
    }
    n = m;

    if (n == 1) {
        fout << 1 << "\n";
        fout << fixed << setprecision(6) << (double)p[0].x << " " << (double)p[0].y << "\n";
        delete[] p;
        return 0;
    }

    // hull are maxim 2*n puncte
    Punct *hull = new Punct[2 * n + 5];
    int H = 0;

    // LOWER hull (de la stanga la dreapta)
    for (int i = 0; i < n; i++) {
        while (H >= 2 && cross(hull[H - 2], hull[H - 1], p[i]) <= 0) {
            H--;
        }
        hull[H++] = p[i];
    }

    // UPPER hull (de la dreapta la stanga)
    int lowerSize = H;
    for (int i = n - 2; i >= 0; i--) {
        while (H > lowerSize && cross(hull[H - 2], hull[H - 1], p[i]) <= 0) {
            H--;
        }
        hull[H++] = p[i];
    }

    // ultimul punct = primul, il eliminam
    if (H > 1) H--;

    // afisare in ordine trigonometrica (CCW)
    fout << H << "\n";
    fout << fixed << setprecision(6);
    for (int i = 0; i < H; i++) {
        fout << (double)hull[i].x << " " << (double)hull[i].y << "\n";
    }

    delete[] hull;
    delete[] p;
    return 0;
}