Cod sursa(job #2777615)

Utilizator George_CristianGeorge Dan-Cristian George_Cristian Data 23 septembrie 2021 19:27:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <valarray>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct {
    long double x, y;
} puncte[120005], stiva[120005];

int n, nstiva, indprimul;

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

long double distanta(punct a, punct b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.x - b.y) * (a.y - b.y));
}

bool comp(punct a, punct b) {
    if (determinant(puncte[0], a, b) == 0)
        return distanta(puncte[0], a) < distanta(puncte[0], b);
    return determinant(puncte[0], a, b) > 0;
}

void citire() {
    f >> n;
    indprimul = 0;
    for (int i = 0; i < n; ++i) {
        f >> puncte[i].x >> puncte[i].y;
        if (puncte[i].x < puncte[indprimul].x ||
            puncte[i].x == puncte[indprimul].x && puncte[i].y < puncte[indprimul].y)
            indprimul = i;
    }
    swap(puncte[0], puncte[indprimul]);
}

void infasuratoare() {
    stiva[0] = puncte[0];
    stiva[1] = puncte[1];
    nstiva = 2;
    for (int i = 2; i < n; ++i) {
        while (determinant(stiva[nstiva - 2], stiva[nstiva - 1], puncte[i]) <= 0)
            nstiva--;
        stiva[nstiva++] = puncte[i];
    }
}

void afisare() {
    g << nstiva << '\n';
    for (int i = 0; i < nstiva; ++i)
        g << fixed << setprecision(6) << stiva[i].x << ' ' << stiva[i].y << '\n';
}

int main() {
    citire();
    sort(puncte + 1, puncte + n, comp);
    infasuratoare();
    afisare();
    return 0;
}