Cod sursa(job #411903)

Utilizator sory1806Sandu Sorina-Gabriela sory1806 Data 5 martie 2010 11:12:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define nmax 120010
#define inf 1000000010
int s[nmax], k, n, i, pmin;
struct coord
{	double x, y;
}	a[nmax], m, z;

int panta_min(coord p1, coord p2)
{	double tmp1, tmp2;
	tmp1=(p1.y-m.y)*(p2.x-m.x)-(p2.y-m.y)*(p1.x-m.x);
//	tmp2=(p1.x-m.x)*(p2.x-m.x);
	if(tmp1<0)	return 1;
	else			return 0;
}

int panta()
{	coord A, B, C;
	double tmp1, tmp2;
	A=a[s[k-1]]; B=a[s[k]]; C=a[i];
	tmp1=(C.y-A.y)*(B.x-A.x)-(C.x-A.x)*(B.y-A.y);
//	tmp2=(C.x-A.x)*(B.x-A.x);
	if(tmp1<0)	return 1;
	else		return 0;
}

int main()
{
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out", "w", stdout);
	
	scanf("%d", &n);
	m.x=inf; m.y=inf;
	for(i=1; i<=n; i++)
	{	scanf("%lf%lf", &a[i].x, &a[i].y);
		if(m.x>a[i].x || (m.x==a[i].x && m.y>a[i].y))	{m.x=a[i].x; m.y=a[i].y; pmin=i;}
	}
	z=a[1]; a[1]=a[pmin]; a[pmin]=z;
	
	sort(a+2, a+n+1, panta_min);
	
	s[1]=1; s[2]=2; k=2;
	for(i=3; i<=n; i++)
	{	while(panta() && k>=2)	k--;
		k++; s[k]=i;
	}
	
	printf("%d\n", k);
	for(i=1; i<=k; i++)
		printf("%lf %lf\n", a[s[i]].x, a[s[i]].y);
	
	return 0;
	
}