Cod sursa(job #2370627)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 6 martie 2019 12:53:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

struct Punct
{
    long double x, y;
};

const int nMax = 120005;

int n;
Punct v[nMax];
int st[nMax], top;

void citire()
{
    ifstream in("infasuratoare.in");
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i].x >> v[i].y;
    in.close();
}

inline long double cross_product(const Punct &o, const Punct &p1, const Punct &p2)
{
    return (p1.x-o.x) * (p2.y-o.y) - (p1.y-o.y) * (p2.x-o.x);
}

inline bool cmp(const Punct &p1, const Punct &p2)
{
    return (cross_product(v[1], p1, p2) < 0);
}

void rezolvare()
{
    for(int i = 2; i <= n; ++i)
        if(v[i].x < v[1].x)
            swap(v[i], v[1]);
    sort(v + 2, v + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    top = 2;

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

void afisare()
{
    ofstream out("infasuratoare.out");
    out << top << "\n";
    out << fixed << setprecision(6);
    for(int i = top; i >= 1; --i)
        out << v[st[i]].x << " " << v[st[i]].y << "\n";
    out.close();
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}