Cod sursa(job #1413993)

Utilizator httpsLup Vasile https Data 2 aprilie 2015 11:35:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
ifstream f("infasuratoare.in");
#define cout g
#else
ifstream f("date.in");
#endif // INFOARENA

ofstream g("infasuratoare.out");

struct punct{double x,y;};

int n,pos,i,st;
punct p[120001],stiva[120001];

double cross_prod(punct A,punct B,punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

inline bool cmp(punct A,punct B)
{
    return cross_prod(p[1],A,B)<0;
}

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
        f>>p[i].x>>p[i].y;
        if(pos==0 || p[pos].x>p[i].x || p[pos].x==p[i].x && p[pos].y>p[pos].y) pos=i;
    }

    swap(p[pos],p[1]);

    sort(p+2,p+n+1,cmp);

    for(i=1;i<=n;++i)
    {
        while(st>1 && cross_prod(stiva[st-1],stiva[st],p[i])<0) --st;
        stiva[++st]=p[i];
    }
    cout<<st<<'\n';
    for(i=1;i<=st;++i) cout<<fixed<<stiva[i].x<<' '<<stiva[i].y<<'\n';

    return 0;
}