Cod sursa(job #2680954)

Utilizator chriss_b_001Cristian Benghe chriss_b_001 Data 4 decembrie 2020 18:07:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <deque>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int INF = (1 << 30);
const int NMAX = 120000;

struct Punct
{
    long double x, y, panta;
};

Punct v[NMAX + 1];
deque <int> Q;

bool cmp(Punct a, Punct b)
{
    return a.panta < b.panta;
}

bool verif_unghi(Punct a, Punct b, Punct c)
{
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x) < 0;
}

inline int calc_panta(int i)
{
    return (v[i].y - v[1].y) / (v[i].x - v[1].x);
}

void afis()
{
    g << Q.size() - 1 << '\n';
    g << fixed << setprecision(6);
    for(int i = 0; i < Q.size() - 1; ++i)
        g << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
}

int main()
{
    int N;
    int MIN = 1;
    f >> N;
    for(int i = 1; i <= N; ++i)
    {
        f >> v[i].x >> v[i].y;
        if(v[i].x < v[MIN].x || (v[i].x == v[MIN].x && v[i].y < v[MIN].y))
            MIN = i;
    }
    swap(v[1], v[MIN]);
    for(int i = 2; i <= N; ++i)
        if(v[i].x == v[1].x) v[i].panta = INF;
        else v[i].panta = calc_panta(i);

    sort(v + 2, v + N + 1, cmp);
    Q.push_back(1);
    Q.push_back(2);

    v[N + 1] = v[1];

    for(int i = 3; i <= N + 1 && Q.front() != Q.back(); ++i)
    {
        while(Q.size() >= 2 && verif_unghi(v[Q[Q.size() - 2]], v[Q[Q.size() - 1]], v[i]))
            Q.pop_back();
        Q.push_back(i);
    }

    afis();

    return 0;
}