Cod sursa(job #1410636)

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

typedef pair<double, double> punct;
punct v[120001], a[100001], xmin, xmax, ymin, ymax;

int n, i, nr, st[100001], k, s;
bool U[100001];

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

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

int main()
{   f>>n;
    for (i=1; i<=n; ++i)
    {   f>>v[i].x>>v[i].y;
        if (i==1)
            xmin=xmax=ymin=ymax=v[i];
        else
        {   if (xmin.x>v[i].x)
                xmin=v[i];
            if (xmax.x<v[i].x)
                xmax=v[i];
            if (ymin.y>v[i].y)
                ymin=v[i];
            if (ymax.y<v[i].y)
                ymax=v[i];
        }
    }
    for (i=1; i<=n; ++i)
        if (isLeft(ymin, xmax, v[i])>=0 || isLeft(xmax, ymax, v[i])>=0 || isLeft(ymax, xmin, v[i])>=0 || isLeft(xmin, ymin, v[i])>=0)
            a[++nr]=v[i];
    sort(a+1, a+nr+1);
    st[1]=1;
    st[2]=2;
    U[2]=1;
    k=2;
    for (i=3, s=1; i>0; i+=(s=(i==nr? -s:s)))
        if (!U[i])
        {   while (k>=2 && isLeft(a[st[k-1]], a[st[k]], a[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<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
    return 0;
}