Cod sursa(job #2379483)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 13 martie 2019 18:10:39
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMax = 120000, oo = 2e9;

int N, K;

struct pct{double x, y;} V[NMax + 5], O, S[NMax + 5];

inline bool compare(pct A, pct B)
{
    return (A.y - O.y) * (B.x - O.x) < (A.x - O.x) * (B.y - O.y);
}

double Det(pct A, pct B, pct C)
{
    return (A.x * B.y + B.x * C.y + C.x * A.y - B.x * A.y - C.x * B.y - A.x * C.y);
}

int main()
{
    fin >> N; O = {oo, oo};

    for(int i = 1; i <= N; i++)
    {
        fin >> V[i].x >> V[i].y;

        if(V[i].y < O.y)
            O = V[i];
        else if(V[i].y == O.y)
            O.x = min(O.x, V[i].x);
    }
    sort(V + 1, V + N + 1, compare);

    S[++K] = V[1], S[++K] = V[2];

    for(int i = 3; i <= N; i++)
    {
        while(K > 1 && Det(S[K], S[K - 1], V[i]) >= 0) K--;

        S[++K] = V[i];
    }
    fout << K << '\n';

    for(int i = 1; i <= K; i++)
        fout << fixed << setprecision(6) << S[i].x << " " << S[i].y << '\n';

    fin.close();
    fout.close();

    return 0;
}