Cod sursa(job #1821266)

Utilizator mihnea00Duican Mihnea mihnea00 Data 2 decembrie 2016 20:48:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>  //pentru zecimale, setprecision se combina cu fixed

using namespace std;

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

int n,i,j,poz,ok;
//bool viz[120010];
struct date
{
    long double x,y;
} v[120110],codi[120110];

long double nebunieunghiularaparametricadeneinteles(date a, date b, date c)
{
    return (c.x-a.x)*(b.y-a.y)-(c.y-a.y)*(b.x-a.x);
}

bool cmp(date a,date b)
{
    return nebunieunghiularaparametricadeneinteles(v[1],a,b)>0;
    /*if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;*/
}

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

    poz=1;
    for(i=2;i<=n;++i)
    {
        if(v[i].x<v[poz].x)
            poz=i;
        else
        {
            if(v[i].x==v[poz].x)
                if(v[i].y<v[poz].y)
                    poz=i;
        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);

    codi[1].x=v[1].x;
    codi[1].y=v[1].y;
    codi[2].x=v[2].x;
    codi[2].y=v[2].y;
    ok=2;
    for(i=3;i<=n;++i)
    {
        while(ok>=2 && nebunieunghiularaparametricadeneinteles(codi[ok-1],codi[ok],v[i])<0)
        {
            //fout<<"da\n";
            --ok;
        }
        ++ok;
        codi[ok].x=v[i].x;
        codi[ok].y=v[i].y;
    }

    fout<<ok<<"\n";
    fout<<fixed<<setprecision(6);
    for(i=ok;i>=1;--i)
    {
        fout<<codi[i].x<<" "<<codi[i].y<<"\n";
    }
    /*fout<<"\n";
    for(i=1;i<=n;++i)
    {
        fout<<v[i].x<<" "<<v[i].y;
        fout<<"\n";
    }
    //fout<<cmp(v[4],v[1]);*/
    return 0;

}