Cod sursa(job #288386)

Utilizator irene_mFMI Irina Iancu irene_m Data 25 martie 2009 19:11:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream.h>
#include <math.h>
#include <iomanip.h>
double x[120000],y[120000],m[120000],pi=3.141592653589793238462643382785,min=0.000000000001;
long n,sol[120000],k,nr;

double unghi(double x,double y)
{
	double sinus,cosinus;
	if(y<min && x<min)
		return 0;
	sinus=double(y/sqrt(y*y+x*x));
	cosinus=double(x/sqrt(y*y+x*x));
	if(cosinus<min)
	{
		if(sinus>min)
			return pi/2;
		else
			if(sinus<min)
				return 3*pi/2;
	}
	else
	{
		if(sinus>min && cosinus>min)
			return atan(sinus/cosinus);
		if(sinus>min && cosinus<min)
			return pi-atan(sinus/(-cosinus));
		if(sinus<=min && cosinus>min)
		{
			if(atan((-sinus)/cosinus)<min)
				return 0;
			return 2*pi-atan((-sinus)/cosinus);
		}
	}
}

void cit()
{
	long i;
	ifstream fin("infasuratoare.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x[i]>>y[i];
		m[i]=unghi(x[i],y[i]);
	}
	fin.close();
}

void minm()
{
	long i,j=1;
	double aux;
	for(i=2;i<=n;i++)
		if(y[i]<y[j] || (y[i]==y[j] && x[i]<x[j]))
			j=i;
	aux=x[j]; x[j]=x[1]; x[1]=aux;
	aux=y[j]; y[j]=y[1]; y[1]=aux;
	aux=m[j]; m[j]=m[1]; m[1]=aux;
}

void poz(long li,long ls)
{
	long ii=0,jj=-1,i=li,j=ls,c;
	double aux;
	while(i<j)
	{
		if(m[i]>m[j] || (((y[i]-y[j]<min && y[i]-y[j]>=0) || (y[j]-y[i]<min && y[j]-y[i]>=0)) && y[i]>y[j]))
		{
			aux=x[i]; x[i]=x[j]; x[j]=aux;
			aux=y[i]; y[i]=y[j]; y[j]=aux;
			aux=m[i]; m[i]=m[j]; m[j]=aux;
			c=ii;
			ii=-jj;
			jj=-c;
		}
		i+=ii;
		j+=jj;
	}
	k=i;
}


void quick(long li,long ls)
{
	if(li<ls)
	{
		poz(li,ls);
		quick(li,k-1);
		quick(k+1,ls);
	}
}

int det(long p1,long p2,long p3)
{
	double d;
	//d=x[p1]*y[p2]+x[p2]*y[p3]+x[p3]*y[p1]-x[p3]*y[p2]-x[p2]*y[p1]-x[p1]*y[p3];
	d=(x[p2]-x[p1])*(y[p3]-y[p1])-(x[p3]-x[p1])*(y[p2]-y[p1]);
	if(d>=0)
		return 0;
	return 1;
}

void rez()
{
	long i;
	nr=3;
	sol[1]=1; sol[2]=2;
	for(i=3;i<=n;i++)
	{
		while(nr>=2 && det(sol[nr],i,sol[nr-1]))
			nr--;
		nr++;
		sol[nr]=i;
	}
	
	while(nr>=3 && det(sol[nr-2],sol[nr-1],sol[nr]))
		nr--;
}

void afis()
{
	long i;
	ofstream fout("infasuratoare.out");
	fout<<nr<<'\n';
	fout.precision(12);
	for(i=1;i<=nr;i++)
		fout<<setiosflags(ios::showpoint)<<x[sol[i]]<<" "<<y[sol[i]]<<'\n';
}

int main()
{
	cit();
	minm();
	quick(2,n);
	rez();
	afis();
	return 0;
}