Cod sursa(job #1013077)

Utilizator timicsIoana Tamas timics Data 20 octombrie 2013 11:12:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<algorithm>
#include <iomanip>
using namespace std;

int N, head;

struct Punct {
    double x,y;
} rez[120005], v[120005];

inline double cross(const Punct& A, const Punct& B, const Punct& C)
{
    return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}

inline int cmp(const Punct& A, const Punct&B)
{
    return cross(v[1],A,B)<0;
}

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

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

    int k=1;
    for(int i=2;i<=N;++i)
    {
        if((v[i].x<v[k].x) || (v[i].x==v[k].y && v[i].y<v[k].y))
        {
            k=i;
        }
    }
    Punct a = v[1];
    v[1] = v[k];
    v[k] = a;

    sort(v+2,v+N+1,cmp);

    rez[1] = v[1];
    rez[2] = v[2];
    head = 2;

    for(int i=3;i<=N;++i)
    {
        while(head>=2 && cross(rez[head - 1], rez[head], v[i])>0)
            --head;
        rez[++head] = v[i];
    }

    fout<<fixed;
    fout<<head<<'\n';
    for(int i=head;i>=1;--i)
        fout<<setprecision(9)<<rez[i].x<<" "<<rez[i].y<<'\n';


    return 0;
}