Cod sursa(job #378423)

Utilizator GotenAmza Catalin Goten Data 28 decembrie 2009 16:49:40
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.81 kb
#include<fstream.h>
#include<iomanip.h>
#include<math.h>

long x[110000],y[110000],b[110000],a[110000],sol[110000];
double xx[110000],yy[110000];

double distance(long i1, long i2)
{
	double l;
	l=(x[i1]-x[i2])*(x[i1]-x[i2])+(y[i1]-y[i2])*(y[i1]-y[i2]);
	return l;
}

void qs(long i, long j)
{
	long s=i,d=j,piv=a[(i+j)>>1],aux;
	while(s<=d)
	{
		while((y[a[s]]-y[1])*(x[piv]-x[1])<(y[piv]-y[1])*(x[a[s]]-x[1])||(y[a[s]]-y[1])*(x[piv]-x[1])==(y[piv]-y[1])*(x[a[s]]-x[1])&&distance(a[s],1)<distance(piv,1))
			s++;
		while((y[a[d]]-y[1])*(x[piv]-x[1])>(y[piv]-y[1])*(x[a[d]]-x[1])||(y[a[d]]-y[1])*(x[piv]-x[1])==(y[piv]-y[1])*(x[a[d]]-x[1])&&distance(a[d],1)>distance(piv,1))
			d--;
		if(s<=d)
		{
			aux=a[s];
			a[s]=a[d];
			a[d]=aux;
			s++;
			d--;
		}
	}
	if(s<j)
		qs(s,j);
	if(i<d)
		qs(i,d);
}

long det(long i1, long i2, long i3)
{
	long r=x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-y[i2]*x[i3]-y[i3]*x[i1]-y[i1]*x[i2];
	return r;
}


void dif(long i1, long i2, long i,double &l)
{
	long semn,k,st,dr;
	double tg,cos,sst,ddr,tg2,sin;
	tg=(y[sol[i1]]-y[sol[i2]])/(x[sol[i1]]-x[sol[i2]]);
	cos=tg*tg+1;
	cos=1/cos;
	sin=1-cos;
	sin=sqrt(sin);
	if(tg>0)semn=0;
	else semn=1;
	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=xx[sol[1]];
	st=1;
	ddr=xx[sol[1]];
	dr=1;
	for(k=2;k<=i;k++)
	{
		if(xx[sol[k]]<sst)
		{
			st=k;
			sst=xx[sol[k]];
		}
		if(xx[sol[k]]>ddr)
		{
			dr=k;
			ddr=xx[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);	
	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;
}
void egale(long i1, long i2, long i,double &l)
{
	long up,down,k;
	double uup,dwn,tg,cos;
	uup=y[sol[1]];
	dwn=y[sol[1]];
	up=1;
	down=1;
	for(k=2;k<=i;k++)
	{
		if(y[sol[k]]>uup)
		{
			up=k;
			uup=y[sol[k]];
		}
		if(y[sol[k]]<dwn)
		{
			down=k;
			dwn=y[sol[k]];
		}
	}
	l=(x[sol[up]]-x[sol[down]])*(x[sol[up]]-x[sol[down]])+(y[sol[up]]-y[sol[down]])*(y[sol[up]]-y[sol[down]]);
	l=sqrt(l);	
	tg=(x[sol[up]]-x[sol[down]])/(y[sol[up]]-y[sol[down]]);
	cos=tg*tg+1;
	cos=1/cos;
	cos=sqrt(cos);
	l*=cos;
}

int main()
{
	long i,j,k=0,n,t=0,inc,sf,aux,i1,i2,i0,uup,up,down,dwn,st,dr;
	double s,smax,numa,numi,l,lmax,sst,ddr,tg,sin,cos;
	ifstream f("rubarba.in");
	ofstream g("rubarba.out");
	f>>n;
	inc=1;
	for(i=1;i<=n;i++)
	{
		f>>x[i]>>y[i];
		if(x[i]<x[inc]||x[i]==x[inc]&&y[i]<y[inc])
			inc=i;
	}
	if(n==1||n==2)
	{
		g<<"0.00";
		return 0;
	}
	if(n==3)
	{
		g<<fixed<<setprecision(2)<<(float)abs(det(1,2,3));
		return 0;
	}
	aux=x[1];
	x[1]=x[inc];
	x[inc]=aux;
	aux=y[1];
	y[1]=y[inc];
	y[inc]=aux;
	for(i=2;i<=n;i++)
		if(x[i]!=x[1])
			a[++k]=i;
		else
			b[++t]=i;
	qs(1,k);
	sf=1;
	for(i=2;i<=t;i++)
		if(y[b[i]]>y[b[sf]])
			sf=i;
	sol[1]=1;
	sol[2]=a[1];
	i=2;j=2;
	while(j<=k)
	{
		while(det(sol[i-1],sol[i],a[j])<=0&&i>1)
			i--;
		sol[++i]=a[j++];
	}
	if(t)
	{
		while(det(sol[i-1],sol[i],b[sf])<=0&&i>1)
			i--;
		sol[++i]=b[sf];
	}
	if(i==1||i==2)
	{
		g<<"0.00";
		return 0;
	}
	if(i==3)
	{
		g<<fixed<<setprecision(2)<<(float)abs(det(sol[1],sol[2],sol[3]));
		return 0;
	}
	smax=(1<<30);
	if(n<10000)
	{
	for(j=1;j<=i;j++)
	{
		i1=j;
		if(j==i)
			i2=1;
		else 
			i2=j+1;
		lmax=0;
		for(i0=1;i0<=i;i0++)
			if(i0!=i1&&i0!=i2)
			{
				numa=(x[sol[i2]]-x[sol[i1]])*(y[sol[i1]]-y[sol[i0]])-(x[sol[i1]]-x[sol[i0]])*(y[sol[i2]]-y[sol[i1]]);
				if(numa<0)
					numa=-numa;
				numi=(x[sol[i2]]-x[sol[i1]])*(x[sol[i2]]-x[sol[i1]])+(y[sol[i2]]-y[sol[i1]])*(y[sol[i2]]-y[sol[i1]]);
				numi=sqrt(numi);
				l=numa/numi;
				if(l>lmax)
					lmax=l;
			}
		if(x[sol[i1]]==x[sol[i2]])
		{
			uup=y[sol[1]];
			dwn=y[sol[1]];
			up=1;
			down=1;
			for(k=2;k<=i;k++)
			{	
				if(y[sol[k]]>uup)
				{
					uup=y[sol[k]];
					up=k;
				}
				if(y[sol[k]]<dwn)
				{
					dwn=y[sol[k]];
					down=k;
				}
			}
			l=(x[sol[down]]-x[sol[up]])*(x[sol[down]]-x[sol[up]])+(dwn-uup)*(dwn-uup);
			l=sqrt(l);
			tg=(float)(x[sol[up]]-x[sol[down]])/(uup-dwn);	
			cos=tg*tg+1;
			cos=1/cos;
			cos=sqrt(cos);
			l*=cos;
		}
		else
		{
			tg=(float)(y[sol[i2]]-y[sol[i1]])/(x[sol[i2]]-x[sol[i1]]);
			cos=tg*tg+1;
			cos=1/cos;
			sin=1-cos;
			sin=sqrt(sin);
			cos=sqrt(cos);
			if(tg<0)
				cos=-cos;
			for(k=1;k<=i;k++)
			{
				xx[sol[k]]=(float)x[sol[k]]*cos+y[sol[k]]*sin;
				yy[sol[k]]=(float)y[sol[k]]*cos-x[sol[k]]*sin;
			}	
			sst=xx[sol[1]];
			ddr=sst;
			st=1;
			dr=1;
			for(k=2;k<=i;k++)
			{
				if(xx[sol[k]]<sst)
				{
					st=k;
					sst=xx[sol[k]];
				}
				if(xx[sol[k]]>ddr)
				{
					dr=k;
					ddr=xx[sol[k]];
				}
			}
			l=(xx[sol[st]]-xx[sol[dr]])*(xx[sol[st]]-xx[sol[dr]])+(yy[sol[st]]-yy[sol[dr]])*(yy[sol[st]]-yy[sol[dr]]);
			l=sqrt(l);	
			tg=(yy[sol[dr]]-yy[sol[st]])/(xx[sol[dr]]-xx[sol[st]]);
			cos=tg*tg+1;
			cos=1/cos;
			cos=sqrt(cos);
			l*=cos;
		}
		s=lmax*l;
		if(s<smax)
			smax=s;
	}
	g<<fixed<<setprecision(2)<<smax;
	}
	else
	{
		for(j=1;j<=i;j++)
				{
				i1=j;
				if(j==i)i2=1;
				else i2=j+1;
				if(x[sol[i1]]==x[sol[i2]])egale(i1,i2,i,l);
				else dif(i1,i2,i,l);
				double dmax=0;
				for(k=1;k<=i;k++)
					if(k!=i1&&k!=i2)
					{
						numa=(x[sol[i2]]-x[sol[i1]])*(y[sol[i1]]-y[sol[k]])-(x[sol[i1]]-x[sol[k]])*(y[sol[i2]]-y[sol[i1]]);
						numi=(x[sol[i2]]-x[sol[i1]])*(x[sol[i2]]-x[sol[i1]])+(y[sol[i2]]-y[sol[i1]])*(y[sol[i2]]-y[sol[i1]]);
						if(numa<0)numa=-numa;
						numi=sqrt(numi);
						double d=numa/numi;
						if(d>dmax)dmax=d;
					}
				s=dmax*l;
				if(j==1)smax=s;
				if(s<smax)smax=s;
				}
			g<<fixed<<setprecision(3)<<smax;
	}
	return 0;
}