Cod sursa(job #378265)

Utilizator GotenAmza Catalin Goten Data 28 decembrie 2009 02:40:45
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.97 kb
#include<fstream.h>
#include<iomanip.h>
#include<math.h>
double x[100100],y[100100],p[100100],xx[100100];
long a[100100],sol[100100],ssol[100100],mi;

void qs(int i, int j)
{
	int s=i,d=j,piv=a[(i+j)>>1],aux;
	while(s<=d)
	{
		while((y[a[s]]-y[mi])*(x[piv]-x[mi])<(y[piv]-y[mi])*(x[a[s]]-x[mi]))
			s++;
		while((y[a[d]]-y[mi])*(x[piv]-x[mi])>(y[piv]-y[mi])*(x[a[d]]-x[mi]))
			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);
}
int det(long q, long w, long 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 2;
	else 
		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;
}
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 max,k,n,j,i,t,b[100100],i1,i2;
	double numa,numi,d,dmax,s,smax,l;
	ifstream f("rubarba.in");
	ofstream g("rubarba.out");
	f>>n>>x[1]>>y[1];
	mi=1;
	t=0;
	for(i=2;i<=n;i++)
	{
		f>>x[i]>>y[i];
		if(x[i]<x[mi]||x[i]==x[mi]&&y[i]<y[mi])mi=i;
	}
	if(n==1||n==2)g<<"0.00";
	else if(n==3) g<<fixed<<setprecision(2)<<fabs(x[1]*y[2]+x[2]*y[3]+x[3]*y[1]-y[1]*x[2]-y[2]*x[3]-y[3]*x[1]);
	else
	{
		k=0;
		for(i=1;i<=n;i++)
			if(x[mi]==x[i])b[++k]=i;
			else 
				{
					p[i]=(y[i]-y[mi])/(x[i]-x[mi]);
					a[++t]=i;
				}
		max=b[1];
		for(i=2;i<=k;i++)
			if(y[b[i]]>y[max])max=b[i];
		qs(1,t);
		ssol[1]=mi;
		ssol[2]=a[1];
		i=2;j=2;
		while(j<=t)
		{
			while(!det(ssol[i-1],ssol[i],a[j]))
				i--;
			ssol[++i]=a[j++];
		}
		if(k>1&&max!=mi)
			ssol[++i]=max;
		while(!det(ssol[i-2],ssol[i-1],ssol[i]))
		{
			ssol[i-1]=ssol[i];
			i--;
		}
		sol[1]=ssol[1];
		sol[2]=ssol[2];
		k=2;
		for(j=3;j<=i;j++)
		{
			if(det(sol[k-1],sol[k],ssol[j])==1)sol[k]=ssol[j];
			else sol[++k]=ssol[j];
		}
		i=k;	
		if(i==1||i==2)g<<"0.00";
		else 
			if(i==3) g<<fixed<<setprecision(2)<<fabs(x[sol[1]]*y[sol[2]]+x[sol[2]]*y[sol[3]]+x[sol[3]]*y[sol[1]]-y[sol[1]]*x[sol[2]]-y[sol[2]]*x[sol[3]]-y[sol[3]]*x[sol[1]]);
			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);
				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);
						d=numa/numi;
						if(d>dmax)dmax=d;
					}
				s=dmax*l;
				if(j==1)smax=s;
				if(s<smax)smax=s;
				cout<<s<<endl;
				}
			g<<fixed<<setprecision(3)<<smax;
			}
	}
	return 0;
}