Cod sursa(job #1156714)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 27 martie 2014 22:04:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
using namespace std;

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

#define cout g
#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define db double
#define pdd pair<db,db>
#define eps 0.0000000000001
#define LE 160666
#include <iomanip>

pdd A[LE];

db CRS(pdd i1,pdd i2,pdd i3)
{
    i2=mp(i2.x-i1.x,i2.y-i1.y);
    i3=mp(i3.x-i1.x,i3.y-i1.y);
    return (i2.y*i3.x-i2.x*i3.y);
}

bool comp(pdd i1,pdd i2)
{
    return (CRS(A[1],i1,i2)>eps);
}

int main()
{
    int i,n,ind;
    f>>n;
    db miny=(1<<30);

    for(i=1; i<=n; ++i)
    {
        f>>A[i].x>>A[i].y;

        if (A[i].y<miny)
            miny=A[i].y,ind=i;
    }

    swap(A[1],A[ind]);
    sort(A+2,A+n+1,comp);
    int K=2;

    for(i=3; i<=n; ++i)
    {
        while (K>1&&CRS(A[K-1],A[K],A[i])<eps) --K;
        A[++K]=A[i];
    }

    cout<<K<<'\n';
    cout<<fixed;
    cout<<setprecision(6);
    cout<<A[1].x<<" "<<A[1].y<<'\n';

    for(i=K; i>1; --i) cout<<A[i].x<<" "<<A[i].y<<'\n';

    return 0;
}