Cod sursa(job #372639)

Utilizator GotenAmza Catalin Goten Data 11 decembrie 2009 00:15:35
Problema Rubarba Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.86 kb
#include<fstream.h>
#include<iomanip.h>
#include<math.h>

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

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,k,n,j,i,t,b[100100],st,dr,semn;
	double numa,numi,d,dmax,s,smax,xx[100100],tg,cos,sin,l,ddr,sst,tg2;
	ifstream f("rubarba.in");
	ofstream g("rubarba.out");
	f>>n>>x[1]>>y[1];
	min=1;
	t=0;
	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<=n;i++)
		if(x[min]==x[i])b[++k]=i;
		else 
			{
				p[i]=(y[i]-y[min])/(x[i]-x[min]);
				a[++t]=i;
			}
	max=b[1];
	for(i=2;i<=k;i++)
		if(y[b[i]]>y[max])max=b[i];
	batman(t);
	sol[1]=min;
	sol[2]=a[1];
	i=2;j=2;
	while(j<=t)
	{
		while(!det(sol[i-1],sol[i],a[j]))i--;
		sol[++i]=a[j++];
	}
	if(k>1&&max!=min)
		sol[++i]=max;
	smax=1000000;
	for(j=1;j<i;j++)
	{
		if(x[sol[j]]==x[sol[j+1]])
		{
			sst=1000001;
			ddr=-1000001;
			for(k=1;k<=i;k++)
				if(k!=j&&k!=j+1)
				{
					if(x[sol[k]]<sst)
					{
						st=k;
						sst=x[sol[k]];
					}
					if(x[sol[k]]>ddr)
					{
						dr=k;
						ddr=x[sol[k]];
					}
				}
		l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[st]]-y[sol[dr]])*(y[sol[st]]-y[sol[dr]]);
		l=sqrt(l);
		tg=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
		cos=tg*tg+1;
		cos=1/cos;
		cos=sqrt(cos);
		l*=cos;
		}
		else
		{
			tg=(y[sol[j+1]]-y[sol[j]])/(x[sol[j+1]]-x[sol[j]]);
			if(tg>0)semn=1;
			else semn=0;
			cos=tg*tg+1;
			cos=1/cos;
			sin=1-cos;
			sin=sqrt(sin);
			cos=sqrt(cos);
			if(!semn)cos=-cos;
			for(k=1;k<=i;k++)
				xx[sol[k]]=x[sol[k]]*cos+y[sol[k]]*sin;		
			sst=1000001;
			ddr=-1000001;
			for(k=1;k<=i;k++)
				if(k!=j&&k!=j+1)
				{
					if(xx[sol[k]]<sst)
					{
						st=k;
						sst=xx[sol[st]];
					}				
					if(xx[sol[k]]>ddr)
					{
						dr=k;
						ddr=xx[sol[dr]];
					}
				}
			l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[dr]]-y[sol[st]])*(y[sol[dr]]-y[sol[st]]);
			l=sqrt(l);
			tg2=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
			tg=(tg2-tg)/(1+tg*tg2);
			cos=tg*tg+1;
			cos=1/cos;
			cos=sqrt(cos);
			l*=cos;
		}		
		dmax=0;
		for(k=1;k<=i;k++)
			if(k!=j&&k!=j+1)
			{
				numa=(x[sol[j+1]]-x[sol[j]])*(y[sol[j]]-y[sol[k]])-(x[sol[j]]-x[sol[k]])*(y[sol[j+1]]-y[sol[j]]);
				numi=(x[sol[j+1]]-x[sol[j]])*(x[sol[j+1]]-x[sol[j]])+(y[sol[j+1]]-y[sol[j]])*(y[sol[j+1]]-y[sol[j]]);
				if(numa<0)numa=-numa;
				numi=sqrt(numi);
				d=numa/numi;
				if(d>dmax)dmax=d;
			}
		s=dmax*l;
		if(s<smax)smax=s;
	}
	if(x[sol[i]]==x[sol[1]])
	{
		sst=1000001;
		ddr=-1000001;
		for(k=2;k<i;k++)
		{
			if(x[sol[k]]<sst)
			{
				st=k;
				sst=x[sol[k]];
			}
			if(x[sol[k]]>ddr)
			{
				dr=k;
				ddr=x[sol[k]];
			}
		}
		l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[st]]-y[sol[dr]])*(y[sol[st]]-y[sol[dr]]);
		l=sqrt(l);
		tg=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
		cos=tg*tg+1;
		cos=1/cos;
		cos=sqrt(cos);
		l*=cos;
	}
	else
	{
		tg=(y[sol[1]]-y[sol[i]])/(x[sol[1]]-x[sol[i]]);
		if(tg>0)semn=1;
		else semn=0;
		cos=tg*tg+1;
		cos=1/cos;
		sin=1-cos;
		sin=sqrt(sin);
		cos=sqrt(cos);
		if(!semn)cos=-cos;
		for(k=1;k<=i;k++)
			xx[sol[k]]=x[sol[k]]*cos+y[sol[k]]*sin;		
		sst=1000001;
		ddr=-1000001;
		for(k=2;k<i;k++)
		{	
			if(xx[sol[k]]<sst)
			{
				st=k;
				sst=xx[sol[st]];
			}				
			if(xx[sol[k]]>ddr)
			{
				dr=k;
				ddr=xx[sol[dr]];
			}
		}
		l=(x[sol[dr]]-x[sol[st]])*(x[sol[dr]]-x[sol[st]])+(y[sol[dr]]-y[sol[st]])*(y[sol[dr]]-y[sol[st]]);
		l=sqrt(l);
		tg2=(y[sol[st]]-y[sol[dr]])/(x[sol[st]]-x[sol[dr]]);
		tg=(tg2-tg)/(1+tg*tg2);
		cos=tg*tg+1;
		cos=1/cos;
		cos=sqrt(cos);
		l*=cos;
	}		
	dmax=0;
	for(k=2;k<i;k++)
	{
		numa=(x[sol[1]]-x[sol[i]])*(y[sol[i]]-y[sol[k]])-(x[sol[i]]-x[sol[k]])*(y[sol[1]]-y[sol[i]]);
		numi=(x[sol[1]]-x[sol[i]])*(x[sol[1]]-x[sol[i]])+(y[sol[1]]-y[sol[i]])*(y[sol[1]]-y[sol[i]]);
		if(numa<0)numa=-numa;
		numi=sqrt(numi);
		d=numa/numi;
		if(d>dmax)dmax=d;
	}
	s=dmax*l;
	if(s<smax)smax=s;
	g<<fixed<<setprecision(2)<<smax;
	return 0;
}