Cod sursa(job #413704)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 8 martie 2010 23:04:23
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<stdio.h>
#include<stdlib.h>
#define nmax 120004


struct asd {long double x; long double y;};
asd nod[nmax];
int n,i,j, index, db=0, que[nmax];
long double minx=9999999, miny=9999999, s;

int cmp(const void *a, const void *b)
{
	return (((asd *)a)->y-miny)*(((asd *)b)->x-minx)>(((asd *)b)->y-miny)*(((asd *)a)->x-minx);
}

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

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);
	for(i=0;i<n;i++)
	{
		scanf("%lf %lf", &nod[i].x, &nod[i].y);
		if(nod[i].x<minx)
		{
			minx=nod[i].x;
			miny=nod[i].y;
			index=i;
		}
		else if(nod[i].x==minx&&nod[i].y<miny)
		{
			minx=nod[i].x;
			miny=nod[i].y;
			index=i;
		}
	}

	qsort(nod, n, sizeof(asd), cmp);
	que[++db]=1;
	que[++db]=2;
	for(i=3;i<n;i++)
	{
		s=semn(que[db-1], que[db], i);
		if(s>0)
			que[++db]=i;
		else 
		{
			while(semn(que[db-1], que[db], i)<0)
				db--;
			que[++db]=i;
		}
	}
	que[++db]=0;
	printf("%d\n", db);
	for(i=1;i<=db;i++)
		printf("%lf %lf\n", nod[i].x,nod[i].y);
	return 0;
}