Cod sursa(job #1372720)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 4 martie 2015 15:07:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
//#include <iostream>
#include <fstream>
using namespace std;

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

#include <iomanip>
#define x first
#define y second
#define mp make_pair
#define db double
#define LE 120666
#define inf (1<<30)
#include <algorithm>
#define cout g
#define eps 0.0000000000001

pair<db,db> A[LE];
int ind[LE],st[LE];

db mul(pair<db,db> ix,pair<db,db> i1,pair<db,db> i2)
{
    i1=mp(i1.x-ix.x,i1.y-ix.y);
    i2=mp(i2.x-ix.x,i2.y-ix.y);
    return i1.y*i2.x-i1.x*i2.y;
}

bool comp(int i1,int i2)
{
    db val=mul(A[1],A[i1],A[i2]);
    if (val>-eps&&val<eps) return A[i1].y>A[i2].y;
    return val>0;
}

int main()
{
    int n,i,imin;
    f>>n;
    pair<db,db> minv=mp(inf,inf);

    for(i=1; i<=n; ++i)
    {
        f>>A[i].x>>A[i].y;
        if (mp(A[i].y,A[i].x)<minv) minv=mp(A[i].y,A[i].x),imin=i;
        ind[i]=i;
    }

    swap(A[imin],A[1]);
    //swap(ind[imin],ind[1]);
    sort(ind+2,ind+n+1,comp);

    st[1]=ind[1];
    st[2]=ind[2];
    int k=2;

    for(i=3; i<=n; ++i)
    {
        while (k>=2&&mul(A[st[k-1]],A[st[k]],A[ind[i]])<-eps) --k;
        st[++k]=ind[i];
    }

    //swap(A[imin],A[1]);

    cout<<fixed;
    cout<<setprecision(10);

    cout<<k<<'\n';

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


    return 0;
}