Cod sursa(job #2176030)

Utilizator vlad6001Pintilie Vlad vlad6001 Data 16 martie 2018 20:30:07
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

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

int nr, contor;

double det(Punct a, Punct b, Punct c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-c.x*b.y-c.y*a.x-a.y*b.x;
}

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

bool cr2(Punct a, Punct b)
{
    return det(punct[1],a,b) < 0;
}

int main()
{
    cin >> nr;
    for(int i=1; i <= nr; i++)
    {
        cin >> punct[i].x >> punct[i].y;
    }
    sort(punct+1, punct+nr+1, cr1);
    sort(punct+2, punct+nr+1, cr2);
    sol[1] = punct[1];
    sol[2] = punct[2];
    sol[3] = punct[3];
    contor = 3;

    for(int i=4; i <= nr; i++)
    {
        while((contor >= 3) && (det(sol[contor-1],sol[contor],punct[i]) > 0))
        contor--;

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