Cod sursa(job #659655)

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

#define inf 2000000000;

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

conv a[100000],st[100000],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);
                }
       }
}

void sortare()
{
    int i,j;
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
            if(a[i].p>a[j].p)
                {
                    double aux=a[i].x;
                    a[i].x=a[j].x;
                    a[j].x=aux;

                    aux=a[i].y;
                    a[i].y=a[j].y;
                    a[j].y=aux;

                    aux=a[i].p;
                    a[i].p=a[j].p;
                    a[j].p=aux;
                }
}

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();
    infasuratoare();
    afisare();
    return 0;
}