Cod sursa(job #2174843)

Utilizator dragos_vecerdeaVecerdea Dragos dragos_vecerdea Data 16 martie 2018 13:46:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

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


struct pereche
{
    double x,y;
};
pereche ales;
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)
{
    return (a.x - ales.x) * (b.y - ales.y) - (a.y - ales.y) * (b.x - ales.x) < 0;
}
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;
    int indice;
    pereche reglaj;
    reglaj.x = 1000000000;
    reglaj.y = 1000000000;
    in >> n;
    for(int i=1;i<=n;i++)
    {
        in >> v[i].x >> v[i].y;
        if(v[i].x<reglaj.x)
        {
            reglaj.x = v[i].x;
            reglaj.y = v[i].y;
            indice = i;
        }
        else if(v[i].x == reglaj.x && v[i].y < reglaj.y)
        {
            reglaj.y = v[i].y;
            indice = i;
        }
    }
    pereche aux;
    aux = v[1];
    v[1] = v[indice];
    v[indice]=aux;
    reglaj = v[1];
    ales = v[1];
    sort(v+2,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(8) << stiva[i].x+reglaj.x <<" "<< stiva[i].y+reglaj.y<<"\n";
    }
    return 0;
}