Cod sursa(job #371854)

Utilizator GotenAmza Catalin Goten Data 7 decembrie 2009 13:16:07
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include<iomanip>
#include<fstream>

using namespace std;

double x[125000],y[125000];
long a[125000],sol[125000],cont,mi;

void qs(long i, long j)
{
	long s=i,d=j,aux,piv=((i+j)>>1);
	while(s<=d)
	{
		while((y[a[s]]-y[mi])*(x[a[piv]]-x[mi])<(y[a[piv]]-y[mi])*(x[a[s]]-x[mi]))s++;
		while((y[a[d]]-y[mi])*(x[a[piv]]-x[mi])>(y[a[piv]]-y[mi])*(x[a[d]]-x[mi]))d--;
		if(s<=d)
		{
			aux=a[s];
			a[s]=a[d];
			a[d]=aux;
			d--;
			s++;
		}
	}
	if(i<d)qs(i,d);
	if(s<j)qs(s,j);
}
	
int det(long i1, long i2, long i3)
{
	if(x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]>y[i1]*x[i2]+y[i2]*x[i3]+y[i3]*x[i1]) return 1;
	else return 0;
}
	
int main()
{ 
	long n,i,j,gasit,k;
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n>>x[1]>>y[1];
	mi=1;
	for(i=2;i<=n;i++)
	{
		f>>x[i]>>y[i];
		if(x[i]<x[mi])mi=i;
		else if(x[i]==x[mi])if(y[i]<y[mi])mi=i;
	}
    a[n]=mi;
	for(i=1;i<mi;i++)a[i]=i;
	a[mi]=n;
	for(i=mi+1;i<n;i++)a[i]=i;
	qs(1,n-1);
	gasit=a[n];
	for(i=n;i>=2;i--)a[i]=a[i-1];
	a[1]=gasit;
	sol[1]=a[1];
	sol[2]=a[2];
	i=1;j=3;
	while(a[j])
	{
		gasit=0;
		while(!gasit&&a[j])
		{
			if(det(sol[i],sol[i+1],a[j]))
			{
				sol[i+2]=a[j];
				i++;
				j++;
				gasit=1;
			}
			else 
			{
				while(!det(sol[i],sol[i+1],a[j]))i--;
				i++;
				sol[i+1]=a[j];
				j++;
			}
		}
	}
	g<<i<<'\n';
	for(j=1;j<=i;j++)g<<fixed<<setprecision(6)<<x[sol[j]]<<' '<<y[sol[j]]<<'\n';
	return 0;
}