Cod sursa(job #669739)

Utilizator mihaidutescuDutescu Mihai mihaidutescu Data 27 ianuarie 2012 17:28:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <cstdlib>

struct point
{
	double x,y;
};

point *a;

int compar_upolar(const void *p1,const void *p2)
{
	if(((*(struct point *)p1).x-a[0].x)*((*(struct point *)p2).y-a[0].y)<((*(struct point *)p1).y-a[0].y)*((*(struct point *)p2).x-a[0].x))
		return 1;
	return 0;
}

inline int isleft(double ax,double ay,double bx,double by)
{
	return ax*by>ay*bx;
}

void citire(int &n)
{
	FILE *f=fopen("infasuratoare.in","r");
	fscanf(f,"%d\n",&n);
	int i=n-1,pinit=0;
	a=(point*)malloc(sizeof(point)*(n));
	fscanf(f,"%lf %lf\n",&a[0].x,&a[0].y);
	while(i)
	{
		fscanf(f,"%lf %lf\n",&a[i].x,&a[i].y);
		if(a[i].x<a[pinit].x||(a[i].x==a[pinit].x&&a[i].y<a[pinit].y))
				pinit=i;
		i--;
	}
	point tmp=a[pinit];
	a[pinit]=a[0];
	a[0]=tmp;
}

void afisare(point* st,int n)
{
    int i;
    FILE* f=fopen("infasuratoare.out","w");
    fprintf(f,"%d\n",n+1);
    for(i=0;i<=n;i++)
        fprintf(f,"%lf %lf\n",st[i].x,st[i].y);
}

point* conv_hull(int n,int &h)
{
	point *st=(point*)malloc(n*sizeof(point));
	int i;
	qsort(a+1,n-1,sizeof(point),compar_upolar);
	st[0]=a[0];
	st[1]=a[1];
	h=1;
	for(i=2;i<n;++i)
	{
		while(!isleft(st[h].x-st[h-1].x,st[h].y-st[h-1].y,a[i].x-st[h].x,a[i].y-st[h].y)) h--;
		++h;
		st[h]=a[i];
	}
	return st;
}

int main()
{
	int n,h;
	point *st;
	citire(n);

	st=conv_hull(n,h);

	afisare(st,h);

	return 0;
}