Cod sursa(job #419894)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 18 martie 2010 10:00:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<stdio.h>
#include<algorithm>
#define inf 1000000010
#define Nmax 121000
struct punct
{
	double x,y;	
}a[Nmax],a0;
int n,k;
 int s[Nmax];
using namespace std;
int compar(punct b,punct c)
{
	return (((c.x-a[0].x)*(b.y-a[0].y)-(b.x-a[0].x)*(c.y-a[0].y))<0);
}

void functie()
{
 s[0]=0;
 s[1]=1;
 k=1;
 for(int i=2;i<n;i++)
 {
	while((a[i].x-a[s[k-1]].x)*(a[s[k]].y-a[s[k-1]].y)-(a[s[k]].x-a[s[k-1]].x)*(a[i].y-a[s[k-1]].y)>0 && k>1)
		k--;
	k++;
	s[k]=i;
 }	 
}

int main()
{
	a0.x=a0.y=inf;
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	int poz;
	for(int i=0;i<n;i++)
	{
		scanf("%lf %lf",&a[i].x,&a[i].y);
		if((a0.x>a[i].x) || ((a0.x==a[i].x) && (a0.y>a[i].y)))
		{	a0=a[i];
			poz=i;
		}
	}
	a[poz]=a[0];
	a[0]=a0;
	sort(a+1,a+n,compar);
	functie();
	printf("%d\n",k+1);
	for(int i=0;i<=k;i++)
	{
		printf("%.6lf %.6lf\n",a[s[i]].x,a[s[i]].y);
	}
	return 0;
}