Cod sursa(job #372084)

Utilizator GotenAmza Catalin Goten Data 8 decembrie 2009 19:14:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<fstream.h>
#include<iomanip.h>

double x[125000],y[125000],p[125000];
long a[125000],sol[125000];

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 n, long k)
{
 long son;
 do
  {
   son=0;
   if(ls(k)<=n)
    {
     son=ls(k);
     if(rs(k)<=n&&p[a[rs(k)]]>p[a[son]])son=rs(k);
     if(p[a[son]]<=p[a[k]])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 batman(int n)
{
	long i;
	bh(n);
	for(i=n;i>1;i--)
	{
		ex(1,i);
		sift(i-1,1);
	}
}

int det(int q, int w, int e)
{
	if(x[q]*y[w]+x[w]*y[e]+x[e]*y[q]>x[w]*y[q]+x[e]*y[w]+x[q]*y[e])return 1;
	else return 0;
}

int main()
{ 
	long min, max=0,k,n,j,i;
	ifstream f("infasuratoare.in");
	ofstream g("infasuratoare.out");
	f>>n>>x[1]>>y[1];
	min=1;
	for(i=2;i<=n;i++)
	{
		f>>x[i]>>y[i];
		if(x[i]<x[min]||x[i]==x[min]&&y[i]<y[min])min=i;
	}
	k=0;
	for(i=1;i<min;i++)
		if(x[i]==x[min])
			max=i;
		else
		{
			p[i]=(y[i]-y[min])/(x[i]-x[min]);
			a[++k]=i;
		}
	for(i=min+1;i<=n;i++)
		if(x[i]==x[min])
			max=i;
		else
		{
			p[i]=(y[i]-y[min])/(x[i]-x[min]);
			a[++k]=i;
		}
	batman(k);
	sol[1]=min;
	sol[2]=a[1];
	i=2;j=2;
	while(j<=k)
	{
		while(!det(sol[i-1],sol[i],a[j]))i--;
		sol[++i]=a[j++];
	}
	if(max)
		sol[++i]=max;
	g<<i<<'\n';
	j=i;
	for(i=1;i<=j;i++)
		g<<fixed<<setprecision(6)<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';
	return 0;
}