Cod sursa(job #3266479)

Utilizator Andercau_VasileAndercau Vasile Andercau_Vasile Data 8 ianuarie 2025 19:49:41
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

#define NMAX 120005

struct punct {
    double x, y;
} p[NMAX];

int st[NMAX], vf;

double det(punct a, punct b, punct c) {
    return a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - a.y * b.x;
}

bool cmp(punct a, punct b) {
    return det(p[1], a, b) > 0;
}

int main() {
    int n;
    fin >> n;
    int minim = 1;
    for (int i = 1; i <= n; ++i) {
        fin >> p[i].x >> p[i].y;

        if (p[i].x < p[minim].x || (p[i].x == p[minim]. x && p[i].y < p[minim]. y)) {
            minim = i;
        }
    }
    swap(p[1], p[minim]);
    sort(p + 2, p + n + 1, cmp);

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

    fout << vf << '\n';
    for (int i = 1; i <= vf; ++i) {
        fout << setprecision(6) << fixed << p[st[i]].x << ' ' << p[st[i]].y << '\n';
    }
    return 0;
}