Cod sursa(job #3358024)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 23:05:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct {
    double x, y;
};

bool cmp(punct a, punct b) {
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

long long det(punct a, punct b, punct c) {
    double val = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (val < 0) return -1;
    if (val > 0) return 1;
    return 0;
}

int main() {
    int n;
    fin >> n;
    punct p[120005];
    for (int i = 0; i < n; ++i) {
        fin >> p[i].x >> p[i].y;
    }

    sort(p, p + n, cmp);

    punct stiva[120005];
    int vf = 0;

    for (int i = 0; i < n; ++i) {
        while (vf >= 2 && det(stiva[vf - 2], stiva[vf - 1], p[i]) <= 0)
            vf--;
        stiva[vf++] = p[i];
    }

    int jos = vf;
    for (int i = n - 2; i >= 0; --i) {
        while (vf > jos && det(stiva[vf - 2], stiva[vf - 1], p[i]) <= 0)
            vf--;
        stiva[vf++] = p[i];
    }

    vf--;
    fout << fixed << setprecision(6);
    fout << vf << "\n";
    for (int i = 0; i < vf; ++i) {
        fout << stiva[i].x << " " << stiva[i].y << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}