Cod sursa(job #1086114)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 17 ianuarie 2014 18:56:35
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
//Infasuratoare convexa
#include <fstream>
#include <math.h>
#include <algorithm>
#define eps 0.00000000001
using namespace std;

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

struct punct
{
    double x,y;
}p[120001],s[120001],aux;


int minp=1,vf,n;

/*
inline double dist(punct A, punct B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)-(A.y-B.y)*(A.y-B.y));
}
*/
bool comp(punct A, punct B)
{
    double u1=(A.y-s[0].y)/(A.x-s[0].x);
    double u2=(B.y-s[0].y)/(B.x-s[0].x);
    return u1<u2;
}
inline double arie2_s(punct A, punct B, punct C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
}

int main()
{
    double d;
    fin>>n;
    for (int i=1;i<=n;++i)
        fin>>p[i].x>>p[i].y;
    for (int i=2;i<=n;++i)
        if (p[minp].x>p[i].x) minp=i;
        else if (p[minp].x==p[i].x)
            if (p[minp].y>p[i].y) minp=i;

    s[0]=p[minp];
    p[minp]=p[1];
    p[1]=s[0];
    sort(p+2,p+n+1,comp);
    s[1]=p[2];
    vf=1;

    for (int i=3;i<=n;++i)
    {
        d=arie2_s(s[vf-1],s[vf],p[i]);
        while (fabs(d)<eps || d<0){
            --vf;
            d=arie2_s(s[vf-1],s[vf],p[i]);
        }
        s[++vf]=p[i];
    }
    fout<<vf+1<<'\n';
    for (int i=0;i<=vf;++i)
        fout<<s[i].x<<" "<<s[i].y<<'\n';
    fin.close();
    fout.close();
    return 0;
}