Cod sursa(job #266067)

Utilizator vladbBogolin Vlad vladb Data 24 februarie 2009 21:19:11
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream.h>

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct punct { double x,y;
	     } a[120100];
int u=1,s[120100];
long n;
double min=1000000000,min1=1000000000;

int sgn(punct b,punct c,punct d)
{
	double semn=((b.x-d.x)*(c.y-d.y)-(b.y-d.y)*(c.x-d.x));
	if(semn>0) return 1;
	if(semn<0) return -1;
	return 0;
}

void sort(int x,int y)
{	int i=x,j=y;
	punct p=a[(i+j)/2],aux;
	do  {
		while(sgn(a[1],a[i],p)==1) ++i;
		while(sgn(a[1],p,a[j])==1) --j;
		if(i<=j) {	aux=a[i];
				a[i]=a[j];
				a[j]=aux;
				++i;
				--j;
			  }
	    } while(i<=j);
	if(x<j)    sort(x,j);
	if(i<y)    sort(i,y);
}

int main()
{       int i;
	fin>>n;
	for(i=1;i<=n;i++)
	{	fin>>a[i].x>>a[i].y;
		if(a[i].y<min){  min=a[i].y;
				 min1=a[i].x;
				 a[0]=a[i];
				 a[i]=a[1];
				 a[1]=a[0];
			      }
			else if(a[i].y==min&&a[i].x<min1)
			     {   min1=a[i].x;
				 a[0]=a[i];
				 a[i]=a[1];
				 a[1]=a[0];
			     }
	}
	sort(2,n);
	s[u]=1;
	for(i=2;i<=n;i++)
	{   	while(u>1&&sgn(a[s[u-1]],a[s[u]],a[i])==-1)
			u--;
		s[++u]=i;
	}
        fout<<u<<"\n";
	for(i=1;i<=u;i++)
		fout<<a[s[i]].x<<" "<<a[s[i]].y<<"\n";
	fin.close();
	fout.close();
	return 0;
}