Cod sursa(job #59545)

Utilizator m_dersidanDersidan Mihai m_dersidan Data 9 mai 2007 18:10:29
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
# include <stdio.h>

# include <math.h>

# define  _fin	"rubarba.in"
# define  _fout	"rubarba.out"

# define  maxn	100001
# define  inf	999999999
# define  PI	3.141592653589

# define  myint	long long


myint x[maxn], y[maxn], o[maxn], b[maxn], n;	// date de intrare
myint q[maxn], h, t;							// stiva pentru infasuratoarea conveax

double a[maxn];								// unghiuri
double minA = -1;

myint i, j, pmin;


inline double dist(myint x, myint y) { return sqrt( x*x + y*y ); }

void intercl(myint st, myint dr)
{
	if (st==dr) return;
	myint m = (st+dr)>>1, i, j, k;
	
	intercl(st, m), intercl(m+1, dr);
	
	for (i=st, j=m+1, k=st; i<=m || j<=dr; )
		if ( i>m || ( j<=dr && a[ o[i] ] > a[ o[j] ] ) )
			b[k++] = o[j++];
		else
			b[k++] = o[i++];
	
	for (i=st; i<=dr; ++i) o[i]=b[i];
}

# define	det(x1,y1,x2,y2,x3,y3) ( x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3 )

# define    cr	q[t]
# define	pr	q[t-1]
# define    th  o[i]

void presolve()
{
	for (i=2,pmin=1; i<=n; ++i)
		if ( y[i]<y[pmin] || (y[i]==y[pmin] && x[i]<x[pmin]) ) pmin=i;

	for (i=1; i<=n; o[i]=i, ++i) {
		if ( i==pmin ) continue;
		a[i] = asin( ( y[i]-y[pmin] ) / dist( x[i]-x[pmin], y[i]-y[pmin] ) );
		if ( x[i]<x[pmin] ) a[i] = PI-a[i];
	}
	
	intercl(1, n);	// punctele ar trebui sa fie sortate dupa unghiul polar

	q[1]=o[1], q[2]=o[2], t=2;

	for (i=3; i<=n; ++i) {
		while ( t>=2 && det( x[cr], y[cr], x[pr], y[pr], x[th], y[th] ) > 0 ) --t;
		q[++t]=o[i];
	}
}

double ABS;
# define    abs(x) ( (ABS=(x)) > 0 ? ABS : -ABS )

void solve()
{
	q[++t]=q[1];

	double A, B, C, div, dx, dy,
		  dl, dr, df, area;

	for (i=1; i<t; ++i) {
		A = y[ q[i+1] ]-y[ q[i] ], B = x[ q[i] ]-x[ q[i+1] ],
		C = x[ q[i] ]*(y[ q[i] ]-y[ q[i+1] ]) + y[ q[i] ]*(x[ q[i+1] ]-x[ q[i] ]);
		div = sqrt( A*A + B*B );
		
		dl=inf, dr=df=-inf;
		
		for (j=1; j<=t; ++j) {
			
			dy = abs(A*x[q[j]] + B*y[q[j]] + C) / div;
			dx = (-B*x[q[j]]+ A*y[q[j]]) / div;

			if ( dl>dx ) dl=dx;
			if ( dr<dx ) dr=dx;
			if ( df<dy ) df=dy;
		}
		
		if ( ( area=df*(dr-dl) ) < minA || minA == -1 ) minA = area;
	}
}

int main()
{
	freopen(_fin, "r", stdin);
	freopen(_fout,"w", stdout);
	
	for (scanf("%lld", &n), i=1; i<=n; ++i) scanf("%lld%lld", x+i, y+i);

	presolve();
	solve();

	printf("%.2f\n", minA);
	
	return 0;
}