Cod sursa(job #277015)

Utilizator hasegandaniHasegan Daniel hasegandani Data 11 martie 2009 14:25:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<stdio.h>
#include<math.h>

#define nmax 1000
#define inf 0x3f3f

int st[nmax],n,k;

struct punct
{
    double x,y;
    float ung;
} a[nmax];

void graham(int i)
{
    if (i<=n)
    {
    st[k+1]=i;
    if (  ((a[st[k]].x-a[st[k+1]].x)*(a[st[k-1]].y-a[st[k]].y) + (a[st[k+1]].y-a[st[k]].y)*(a[st[k-1]].x-a[st[k]].x))>=0  )
        {
        st[k]=i;
        graham(i+1);
        }
    else
        {
        ++k;
        graham(i+1);     
        }
    }
}


void sort(int st,int dr)
{
    if (st>=dr)
        return ;
    else
        {
        int poz=st-1;
        for(int i=st;i<=dr;++i)
            if (a[i].ung<=a[dr].ung)
                {
                    punct aux=a[i];
                    a[i]=a[++poz];
                    a[poz]=aux;
                }
                
        sort(st,poz-1);
        sort(poz+1,dr);
        }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    scanf("%d",&n);
    int min=inf,pmin;
    for(int i=1;i<=n;++i)
	{
	scanf("%lf%lf",&a[i].x,&a[i].y);
	if (min>a[i].y)
	    {
		min=a[i].y;
		pmin=i;
	    }
	else
	if (min==a[i].y && a[pmin].x > a[i].x)
		pmin=i;
	}

    for(int i=1;i<=n;++i)
	{
	    if (a[i].x == a[pmin].x)
		if (pmin!=i)
			a[i].ung=90;
		else
			a[i].ung=-1;
	    else
		{
		a[i].ung=atan( double((a[i].y - a[pmin].y)) / (a[i].x - a[pmin].x)  );
		a[i].ung=(a[i].ung*180)/M_PI;
		if (a[i].ung<0)
                	a[i].ung=a[i].ung+180;
		}
        }

    sort(1,n);

    st[1]=1;
    st[2]=2;
    st[3]=3;
    
    k=3;
    graham(4);
    
    printf("%d\n",k);
    for(int i=1;i<=k;++i)
        printf("%.6f %.6f\n",a[st[i]].x,a[st[i]].y);
    return 0;
}