Cod sursa(job #326833)

Utilizator AndreyPAndrei Poenaru AndreyP Data 26 iunie 2009 12:47:45
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.1 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<bitset>
#include<algorithm>
using namespace std;
#define mp make_pair
#define fs first
#define sc second
#define N 100010
#define pdd pair<double,double>
const double eps=1e-12;
const double lim=0.785398163397;
int n,st[N];
double A,B,C,rez=-1;
pdd v[N];
bitset<N> uz;
inline char cmp(double x,double y)
{
	if(x+eps<y)
		return -1;
	if(y+eps<x)
		return 1;
	return 0;
}
inline char semn(pdd a,pdd b,pdd c)
{
	double A=a.sc-b.sc,B=b.fs-a.fs,C=a.fs*b.sc-b.fs*a.sc;
	return cmp(A*c.fs+B*c.sc+C,0);
}
inline double modul(double x)
{
	if(x<0)
		return -x;
	return x;
}
inline double distanta(pdd a,pdd b)
{
	return sqrt((a.fs-b.fs)*(a.fs-b.fs)+(a.sc-b.sc)*(a.sc-b.sc));
}
inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%lf%lf",&v[i].fs,&v[i].sc);
	sort(v+1,v+n+1);
}
inline void infasuratoare()
{
	int k=2;
	st[1]=1;
	st[2]=2;
	uz[2]=1;
	int pas=1,i=3;
	while(uz[1]==0)
	{
		while(uz[i])
		{
			if(i==n)
				pas=-1;
			i+=pas;
		}
		while(k>1 && semn(v[st[k-1]],v[st[k]],v[i])==-1)
		{
			uz[st[k]]=0;
			--k;
		}
		st[++k]=i;
		uz[i]=1;
	}
	st[0]=k;
}
inline double afla(pdd p,double &dist)
{
	double d=modul(A*p.fs+B*p.sc+C);
	d*=d;
	d/=(A*A+B*B);
	dist=sqrt(d);
	double A1=-B;
	double B1=A;
	double C1=A*p.sc-B*p.fs;
	double x=(C1*B-C*B1)/(A*B1-A1*B);
	return x;
}
inline double afla1(pdd p,double &dist)
{
	double d=modul(A*p.fs+B*p.sc+C);
	d*=d;
	d/=(A*A+B*B);
	dist=sqrt(d);
	double A1=-B;
	double B1=A;
	double C1=A*p.sc-B*p.fs;
	double y=(A*C1-A1*C)/(B*A1-B1*A);
	return y;
}
inline void rezolva()
{
	double xmin,xmax,y;
	int cy;
	double s;
	for(int i=1; i<st[0]; ++i)
	{
		A=v[st[i]].sc-v[st[i+1]].sc;
		B=v[st[i+1]].fs-v[st[i]].fs;
		C=v[st[i]].fs*v[st[i+1]].sc-v[st[i+1]].fs*v[st[i]].sc;
		if(A==0 && B==0)
			exit(4);
		if(A!=0 && B!=0)
		{
			double unghi=atan(-A/B);
			if(cmp(unghi,lim)!=1)
			{
				double dist;
				double x=afla(v[st[1]],dist);
				y=dist;
				xmin=xmax=x;
				cy=st[1];
				for(int j=2; j<st[0]; ++j)
				{
					x=afla(v[st[j]],dist);
					if(cmp(dist,y)==1)
					{
						y=dist;
						cy=st[j];
					}
					if(cmp(x,xmin)==-1)
						xmin=x;
					if(cmp(x,xmax)==1)
						xmax=x;
				}
				double ymin=(-A*xmin-C)/B;
				double ymax=(-A*xmax-C)/B;
				pdd aux1=mp(xmax,ymax),aux2=mp(xmin,ymin);
				s=y*distanta(aux1,aux2);
			}
			else
			{
				double dist;
				double y=afla1(v[st[1]],dist);
				double x=dist;
				double ymin=y,ymax=y;
				int cx=st[1];
				for(int j=2; j<st[0]; ++j)
				{
					y=afla1(v[st[j]],dist);
					if(cmp(dist,x)==1)
					{
						x=dist;
						cx=st[j];
					}
					if(cmp(y,ymin)==-1)
						ymin=y;
					if(cmp(y,ymax)==1)
						ymax=y;
				}
				xmin=(-B*ymin-C)/A;
				xmax=(-B*ymax-C)/A;
				pdd aux1=mp(xmax,ymax),aux2=mp(xmin,ymin);
				s=x*distanta(aux1,aux2);
			}
		}
		else
		if(A==0)
		{
			double y=-C/B;
			xmin=xmax=v[st[1]].fs;
			double dif=modul(v[st[1]].sc-y);
			cy=st[1];
			for(int j=2; j<st[0]; ++j)
			{
				if(v[st[j]].fs<xmin)
					xmin=v[st[j]].fs;
				if(v[st[j]].fs>xmax)
					xmax=v[st[j]].fs;
				double aux=modul(v[st[j]].sc-y);
				if(cmp(aux,dif)==1)
				{
					dif=aux;
					cy=st[j];
				}
			}
			s=dif*(xmax-xmin);
		}
		else
		{
			double ymax,ymin;
			ymax=ymin=v[st[1]].sc;
			double x=-C/A;
			int cx=1;
			double dif=modul(v[st[1]].fs-x);
			for(int j=2; j<st[0]; ++j)
			{
				if(v[st[j]].sc<ymin)
					ymin=v[st[j]].sc;
				if(v[st[j]].sc>ymax)
					ymax=v[st[j]].sc;
				double aux=modul(v[st[j]].fs-x);
				if(cmp(aux,dif)==1)
				{
					dif=aux;
					cx=st[j];
				}
			}
			s=dif*(ymax-ymin);
		}
		if(rez==-1)
			rez=s;
		else
		if(cmp(rez,s)==1)
			rez=s;
	}
	printf("%lf\n",rez);
}
int main()
{
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	citire();
	if(n<3)
	{
		printf("0.000000\n");
		return 0;
	}
	infasuratoare();
	//for(int i=1; i<st[0]; ++i)
	//	printf("%lf %lf\n",v[st[i]].fs,v[st[i]].sc);
	//printf("\n");
	rezolva();
	return 0;
}