Cod sursa(job #1905826)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 6 martie 2017 11:09:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iomanip>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");


struct pereche
{
    double x,y;
};
pereche v[120005];
pereche stiva[120005];
bool sortare (pereche a , pereche b)
{
    if(a.x<b.x) return true;
    if(a.x == b.x)
    {
        if(a.y <= b.y) return true;
        return false;
    }
    return false;
}
bool panta (pereche a, pereche b)
{
    if(a.x == 0 && b.x!=0) return true;
    if(a.x == 0 && b.x==0 && a.y<=b.y) return true;
    if((double)a.y/a.x > (double)b.y/b.x) return true;
    return false;
}
double determinant(pereche A, pereche B, pereche C)
{
     return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int main()
{
    int n;
    in >> n;
    for(int i=1;i<=n;i++)
    {
        in >> v[i].x >> v[i].y;
    }
    sort(v+1,v+n+1,sortare);
    pereche reglaj = v[1];
    for(int i=1;i<=n;i++)
    {
        v[i].x = v[i].x - reglaj.x;
        v[i].y = v[i].y - reglaj.y;
    }
    sort(v+1,v+n+1,panta);
    stiva[1]=v[1];
    stiva[2]=v[2];
    int vf = 2;
    for(int i=3;i<=n;i++)
    {
        while(determinant(stiva[vf-1], stiva[vf], v[i]) > 0 && vf>=2)
        {
            vf--;
        }
        vf++;
        stiva[vf] = v[i];
    }
    out << vf <<"\n";
    for(int i=vf;i>=1;i--)
    {
        out<<fixed;
        out<<setprecision(12) << stiva[i].x+reglaj.x <<" "<< stiva[i].y+reglaj.y<<"\n";
    }
    return 0;
}