Cod sursa(job #371974)

Utilizator GotenAmza Catalin Goten Data 7 decembrie 2009 23:03:51
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include<fstream.h>
#include<iomanip.h>

using namespace std;

double x[125000],y[125000],val1,val2;
long a[125000],sol[125000],mi,n;

long ls(long k)
{
 return (k<<1);
 }
long rs(long k)
{
 return ((k<<1)+1);
 }
long f(long k)
{
 return (k>>1);
 }

void ex(long x, long y)
{
 long aux;
 aux=a[x];
 a[x]=a[y];
 a[y]=aux;
 }


void sift(long nn, long k)
{
 long son;
 do
  {
   son=0;
   if(ls(k)<=nn)
    {
     son=ls(k);
     if(rs(k)<=nn&&(y[a[rs(k)]]-y[n])/(x[a[rs(k)]]-x[n])>(y[a[son]]-y[n])/(x[a[son]]-x[n]))son=rs(k);
     if((y[a[son]]-y[n])/(x[a[son]]-x[n])<=(y[a[k]]-y[n])/(x[a[k]]-x[n]))son=0;
     }
   if(son)
    {
     ex(k,son);
     k=son;
     }
    }
   while(son);
 }

void bh(long n)
{
 long i;
 for(i=(n>>1);i;i--)sift(n,i);
 }

void heapsort(int n)
{
	long i;
	bh(n);
	for(i=n;i>1;i--)
	{
		ex(1,i);
		sift(i-1,1);
	}
}
	
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 i,j;
	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;
	}
	val1=x[mi];
	val2=y[mi];
	for(i=mi;i<n;i++){x[i]=x[i+1];y[i]=y[i+1];}
	x[n]=val1;
	y[n]=val2;
	for(i=1;i<=n;i++)a[i]=i;
    heapsort(n-1);
	for(i=1;i<=n;i++)cout<<x[a[i]]<<' '<<y[a[i]]<<endl;
	sol[1]=a[n];
	sol[2]=a[1];
	i=2;j=2;
	while(j<n)
	{
		if(det(sol[i-1],sol[i],a[j]))sol[++i]=a[j++];			
		else
		{
			while(!det(sol[i-1],sol[i],a[j]))i--;
			sol[++i]=a[j++];
		}
	}
	g<<i<<'\n';
	for(j=1;j<=i;j++)g<<fixed<<setprecision(6)<<x[sol[j]]<<' '<<y[sol[j]]<<'\n';
	return 0;
}