Cod sursa(job #1410642)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 31 martie 2015 10:35:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second
using namespace std;

typedef pair<double, double> punct;
punct v[NMAX];
int n, i, j, st[NMAX], s, k;
bool U[NMAX];

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

double isLeft(punct p0, punct p1, punct p2)
{   return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}

int main()
{   f>>n;
    for (i=1; i<=n; ++i)
        f>>v[i].x>>v[i].y;
    sort(v+1, v+n+1);
    st[1]=1;
    st[2]=2;
    k=2;
    U[2]=1;
    for (i=3, s=1; i>0; i+=(s=(i==n ? -s:s)))
        if (!U[i])
        {   while (k>=2 && isLeft(v[st[k-1]], v[st[k]], v[i])<=0)
                U[st[k--]]=0;
            st[++k]=i;
            U[i]=1;
        }
    g<<k-1<<'\n';
    g<<setprecision(6)<<fixed;
    for (i=1; i<k; ++i)
        g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    return 0;
}