Cod sursa(job #326818)

Utilizator AndreyPAndrei Poenaru AndreyP Data 26 iunie 2009 10:37:12
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 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-7;
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;
	/*double a=A*A+B*B;
	double b=-2*p.fs*B*B+2*A*C+2*p.sc*A*B;
	double c=-d*B*B+B*B*p.fs*p.fs+p.sc*p.sc*B*B+2*p.sc*B*C+C*C;
	double delta=b*b-4*a*c;
	if(cmp(delta,0)!=0)
	{
		//printf("Nu prea e bine :( , delta = %lf\n",delta);
		exit(4);
	}
	double x=-b/(2*a);
	dist=sqrt(d);
	return x;*/
}
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)
		{
			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
		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=(modul(y-v[cy].sc))*(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=(modul(x-v[cx].fs))*(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;
}