Cod sursa(job #659675)

Utilizator aldulea_cristialdulea cristi aldulea_cristi Data 10 ianuarie 2012 20:48:08
Problema Infasuratoare convexa Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 2.36 kb
#include <stdio.h>
#include <stdlib.h>

#define inf 2000000000;

typedef struct conv
{
    double x,y,p;
}conv;

conv a[120001],st[120001],m;
int n,poz,nr=2;

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

void panta()
{
    int i;
    for(i=0;i<n;i++)
       {
           if(a[i].x==m.x)
                {
                    a[i].p=inf;
                }
            else
                {
                    a[i].p=(a[i].y-m.y)/(a[i].x-m.x);
                }
       }
}

int partitionare(int st,int dr,conv a[])
{
    int j=dr+1,i=st-1,ok=1,k;

    double pivot;
    pivot=a[st].p;

    do
    {
        do
        {
            j--;
        }
        while(a[j].p>pivot);

        do
        {
            i++;
        }
        while(a[i].p<pivot);

        if(i<j)
            {
                conv aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
        else
            {
                ok=0;
                k=j;
            }
    }
    while(ok==1);
    return k;

}

void sortare(conv a[],int st,int dr)
{
    if(st<dr)
        {
            int p=partitionare(st,dr,a);
            sortare(a,st,p);
            sortare(a,p+1,dr);
        }
}

int det(conv a,conv b,conv c)
{
    double d=a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
    if(d>=0)
        return 1;
    return 0;
}

void infasuratoare()
{
    st[0]=m;
    st[1]=a[0];
    int i;
    for(i=1;i<n;i++)
        if(det(st[nr-2],st[nr-1],a[i])==1)
            st[nr++]=a[i];
        else
            {
                while(det(st[nr-2],st[nr-1],a[i])==0)
                    st[--nr]=a[i];
                nr++;
            }
}

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

int main()
{
    citire();
    panta();
    sortare(a,0,n-1);
    infasuratoare();
    afisare();
    return 0;
}