Cod sursa(job #1096724)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 2 februarie 2014 15:51:48
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
#define x first
#define y second

using namespace std;

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

typedef pair<double,double> punct;

punct a[120001];
punct st[120001];

double rotation(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);
}

bool cmp(const punct& A,const punct& B)
{
    return rotation(a[1],A,B)<0;
}



int main()
{
    int n;
    fin>>n;
    int pos = 1;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        if(a[i] < a[pos])
            pos = i;
    }
    swap(a[1],a[pos]);
    sort(a+2,a+1+n,cmp);
    st[1] = a[1];
    st[2] = a[2];
    int k = 2;
    for(int i=3;i<=n;i++)
    {
        while(k>=2 && rotation(st[k-1],st[k],a[i])>0)
            --k;
        st[++k] = a[i];
    }
    fout<<k<<'\n';
    for(int i=k;i>0;i--)
        fout<<setprecision(9)<<fixed<<st[i].x<<' ' <<st[i].y<<'\n';


    fin.close();
    fout.close();
    return 0;
}