Cod sursa(job #720595)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 22 martie 2012 19:30:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
#include<algorithm>
#define INF 1e9+5
#define NMax 120005
using namespace std;

double x[NMax],y[NMax];
int v[NMax],n,p0,st[NMax];

bool cmp (int i,int j)
{
    return (double)(x[i]-x[p0])*(y[j]-y[p0])<(double)(x[j]-x[p0])*(y[i]-y[p0]);
}

long double semn (int x1,int x2,int x3)
{
    return (long double)(x[x2]-x[x1])*(y[x3]-y[x1])-(x[x3]-x[x1])*(y[x2]-y[x1]);
}

void citire ()
{
    freopen("infasuratoare.in","r",stdin);
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
        if (y[i]<y[p0] || (y[i]==y[p0] && x[i]<x[p0]))
            p0=i;
    }
}

void sortare ()
{
    int i;
    for (i=1; i<=n; i++)
        if (i!=p0)
            v[++v[0]]=i;
    sort(v+1,v+v[0]+1,cmp);
}

void scanare_graham ()
{
    st[0]=3; st[1]=p0;
    st[2]=v[1]; st[3]=v[2];
    for (int i=3; i<=v[0]; i++)
    {
        while (semn(st[st[0]-1],st[st[0]],v[i])>0) st[0]--;
        st[++st[0]]=v[i];
    }
}

void afisare ()
{
    freopen("infasuratoare.out","w",stdout);
    printf("%d\n",st[0]);
    printf("%lf %lf\n",x[p0],y[p0]);
    reverse(st+1,st+st[0]+1);
    for (int i=1; i<st[0]; i++)
        printf("%lf %lf\n",x[st[i]],y[st[i]]);
}

int main ()
{
    x[0]=INF; y[0]=INF;
    citire();
    sortare();
    scanare_graham();
    afisare();
    return 0;
}