Cod sursa(job #1344001)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 16 februarie 2015 10:20:08
Problema Infasuratoare convexa Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <cstdio>
#include <algorithm>
#define Nmax 120005
using namespace std;

ofstream g("infasuratoare.out");

long n,i,r[Nmax];

struct Punct{
    double x,y;
    long poz,uz;
};
Punct v[Nmax];

bool comp(Punct a,Punct b)
{
    return a.y<b.y || (a.y==b.y && a.x>b.x);
}

double ad(Punct a,Punct b,Punct p)
{
    return a.x*b.y+b.x*p.y+p.x*a.y-p.x*b.y-a.x*p.y-b.x*a.y;
}

bool valid(Punct a,Punct b,Punct c)
{
    if (ad(a,b,c)<0)
        return 0;
    return 1;
}

void infasoara()
{
    long stiva[Nmax];
    int i=1;
    int j=2;

    stiva[1]=1;
    stiva[2]=2;
    i=2;
    while (stiva[i]!=n)
    {
        j++;
        while (valid(v[stiva[i-1]],v[stiva[i]],v[j])==0)
            i--;
        i++;
        stiva[i]=j;
    }
    while (stiva[i]!=1)
    {
        j--;
        while (valid(v[stiva[i-1]],v[stiva[i]],v[j])==0)
            i--;
        i++;
        stiva[i]=j;
    }
    r[0]=i;
    for (j=1;j<=i;j++)
        r[j]=stiva[j];
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%ld",&n);

    for (i=1;i<=n;i++)
        scanf("%lf%lf",&v[i].x,&v[i].y),v[i].poz=i;

    sort(v+1,v+n+1,comp);

    infasoara();

    r[0]--;

    g<<r[0]<<'\n';

    for (i=1;i<=r[0];i++)
    {
        g.precision(6);
        g<<fixed<<v[r[i]].x<<' '<<fixed<<v[r[i]].y<<'\n';
    }
    g.close();
    return 0;
}