Cod sursa(job #2986809)

Utilizator andu9andu nita andu9 Data 1 martie 2023 11:37:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

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

const int nMax = 12e4 + 1;

struct point {
    double x, y;
}v[nMax], stiva[nMax];

int n, Size;

double crossProduct (point a, point b, point c) {
    return (a.x - b.x) * (b.y - c.y) - (a.y - b.y) * (b.x - c.x);
}

bool cond (point a, point b) {
    return crossProduct (v[1], a, b) < 0;
}

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


    int pos = 1;
    for (int i = 2; i <= n; i += 1)
        if (v[i].x < v[pos].x)
            pos = i;
    std::swap (v[1], v[pos]);
    std::sort (v + 2, v + 1 + n, cond);


    Size = 2;
    stiva[1] = v[1], stiva[2] = v[2];
    for (int i = 3; i <= n; i += 1) {
        while (Size >= 2 && crossProduct (stiva[Size - 1], stiva[Size], v[i]) > 0)
            Size -= 1;
        Size += 1, stiva[Size] = v[i];
    }


    fout << Size << '\n';
    for (int i = Size; i >= 1; i -= 1)
        fout << std::fixed << std::setprecision (9) << stiva[i].x << ' ' << stiva[i].y << '\n';
    return 0;
}