Cod sursa(job #1529105)

Utilizator dorin31Geman Dorin Andrei dorin31 Data 20 noiembrie 2015 15:33:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <iomanip>
#include <algorithm>

#define x first
#define y second

using namespace std;

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

int n,top,pos,S[120010];

typedef pair <double, double> Tip;
Tip v[120010];

double Det(Tip a, Tip b, Tip c)
{
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

bool cmp(Tip a, Tip b)
{
    return (Det(v[1], a, b)<0);
}

int main()
{

    fin>>n;
    pos=1;
    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
        if (v[i]<v[pos]) pos=i;
    }
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
    S[++top]=1;
    for (int i=2; i<=n; ++i)
    {
        while (top>1 && Det(v[S[top-1]],v[S[top]],v[i])>0) top--;
        S[++top]=i;
    }
    fout<<top<<'\n';
    while (top) {
        fout<<fixed<<setprecision(6)<<v[S[top]].x<<" "<<v[S[top]].y<<'\n';
        top--;
    }
    return 0;
}