Cod sursa(job #1341413)

Utilizator sorynsooSorin Soo sorynsoo Data 12 februarie 2015 18:39:33
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;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct rct
{
    double first,second;
}pc[120002],aux;

int n,m,stiva[120002],varf,minim;

double semn(rct x,rct y,rct z)
{
    return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}

bool compara(rct x,rct y)
{
    return semn(pc[1],x,y)>0;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>pc[i].first>>pc[i].second;
        if(pc[i].second < pc[minim].second)
            minim=i;
        else
            if(pc[i].second==pc[minim].second && pc[i].first<pc[minim].first)
                minim=i;
    }

    aux=pc[1];
    pc[1]=pc[minim];
    pc[minim]=aux;


    sort(pc+2,pc+n+1,compara);
    for(int i=1;i<=n;i++)
    {
        while(varf>=2 && semn(pc[i],pc[stiva[varf]],pc[stiva[varf-1]]) > 0 )
            varf--;
        stiva[++varf]=i;
    }

    cout<<varf<<'\n';

    for(int i=1;i<=varf;i++)
        cout<<fixed<<setprecision(12)<<pc[stiva[i]].first<<" "<<pc[stiva[i]].second<<'\n';
    return 0;
}