Cod sursa(job #601452)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 iulie 2011 18:39:15
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NMAX 100005
#define alfa 0.00001
#define pdd pair <double,double>
#define x first
#define y second
using namespace std;
int n,r,touch;
pdd A[NMAX],st[NMAX];
double rez;
bool comp(pdd a,pdd b)
{
	if (a.y<b.y)
		return 1;
	if (a.y>b.y)
		return 0;
	if (a.x<b.x)
		return 1;
	return 0;
}
inline int semn(pdd a,pdd b,pdd c)
{
	double A=a.y-b.y;
	double B=b.x-a.x;
	double C=a.x*b.y-b.x*a.y;
	return (A*c.x+B*c.y+C)<0;
}
inline double modul(double x)
{
	return x<0 ? -x : x;
}
inline double min(double x,double y)
{
	return x<y ? x : y;
}
int main()
{
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	scanf("%d",&n);
	int i,j,which,poz1,poz2;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&A[i].x,&A[i].y);
	double v1=cos(alfa),v2=sin(alfa),v3,v4;
	for (i=1; i<=n; i++)
	{
		v3=A[i].x*v1-A[i].y*v2;
		v4=A[i].y*v1+A[i].x*v2;
		A[i].x=v3; A[i].y=v4;
	}
	sort(A+1,A+n+1,comp);
	st[++r]=A[1]; st[++r]=A[2];
	for (i=3; i<=n; i++)
	{
		while (r>=2 && semn(st[r-1],st[r],A[i]))
			r--;
		st[++r]=A[i];
	}
	for (i=n-1; i>=1; i--)
	{
		while (r>=2 && semn(st[r-1],st[r],A[i]))
			r--;
		st[++r]=A[i];
	}
	st[0]=st[r-1]; st[r+1]=st[2];
	double A,B,C,A2,B2,C2,val,val2,best,best2;
	for (i=1; i<r; i++)
	{
		A=st[i].y-st[i+1].y;
		B=st[i+1].x-st[i].x;
		C=st[i].x*st[i+1].y-st[i+1].x*st[i].y;
		val=sqrt(A*A+B*B); best=0;
		for (j=1; j<=r; j++)
			if (j!=i && j!=i+1)
			{
				val2=modul(A*st[j].x+B*st[j].y+C);
				if (val2>best)
					best=val2,which=j;
			}
		best/=val;
		A2=-B;
		B2=A;
		val2=sqrt(A2*A2+B2*B2);
		v1=v2=A2*st[1].x+B2*st[1].y; poz1=poz2=1;
		for (j=2; j<=r; j++)
		{
			if (A2*st[j].x+B2*st[j].y>v1)
				v1=A2*st[j].x+B2*st[j].y,poz1=j;
			if (A2*st[j].x+B2*st[j].y<v2)
				v2=A2*st[j].x+B2*st[j].y,poz2=j;
		}
		C2=-A2*st[poz1].x-B2*st[poz1].y;
		best2=modul(A2*st[poz2].x+B2*st[poz2].y+C2)/val2;
		if (!touch)
			rez=best*best2,touch=1;
		else
			rez=min(rez,best*best2);
	}
	printf("%.2lf\n",rez);
	return 0;
}