Cod sursa(job #2280032)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 10 noiembrie 2018 11:05:30
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int nr, contor;

struct Punct
{
    double x, y;
}v[120004], sol[120004];

bool f1(Punct a, Punct b)
{
    if(a.x != b.x)
    return a.x < b.x;
    return a.y < b.y;
}

double determinant(Punct p, Punct a, Punct b)
{
    double CP;
    CP = (a.x - p.x)*(b.y-p.y)-(b.x*p.x)*(a.y-p.y);
    return CP;
}

bool f2(Punct a, Punct b)
{
    return determinant(a, b, v[1]) < 0;
}

int main()
{
    cin >> nr;
    for(int i=1; i <= nr; i++)
    {
        cin >> v[i].x >> v[i].y;
    }

    sort(v+1, v+nr+1, f1);
    sort(v+2, v+nr+1, f2);
    sol[1] = v[1];
    sol[2] = v[2];
    sol[3] = v[3];
    contor = 3;

    for(int i=4; i <= nr; i++)
    {
        while(determinant(sol[contor], v[i], sol[contor-1]) > 0)
        contor--;

        contor++;
        sol[contor] = v[i];
    }

    cout << contor << '\n';
    for(int i=contor; i > 0; i--)
    {
        cout << fixed << setprecision(13) << sol[i].x << ' ' << sol[i].y << '\n';
    }
}