Cod sursa(job #1211912)

Utilizator nicol.bolasNicol Bolas nicol.bolas Data 23 iulie 2014 14:48:05
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
#define NMAX 120005
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    double x,y;
} aux,a[NMAX],st[NMAX];
int n,p,k;
double det(punct A, punct B, punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
bool cmp(punct A, punct B)
{
    return (det(a[1],A,B)>0);
}
int main()
{
    int i;
    fin>>n;
    for (i=1;i<=n;++i)
        fin>>a[i].x>>a[i].y;
    p=1;
    for (i=2;i<=n;++i)
        if (a[i].x<a[p].x) p=i;
    aux=a[1], a[1]=a[p], a[p]=aux;
    sort(a+2,a+n+1,cmp);
    st[1]=a[1], st[2]=a[2], k=2;
    for (i=3;i<=n;++i)
    {
        while (k>1 && det(a[i],st[k],st[k-1])>0)
            --k;
        st[++k]=a[i];
    }
    fout<<k<<"\n";
    for (i=1;i<=k;++i)
        fout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<"\n";
    return 0;
}