Cod sursa(job #536656)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 18 februarie 2011 22:16:21
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define Nmax 100010
#define ll long long
#define Inf (ll)1<<60
using namespace std;

struct punct { ll x , y ; double panta ; } v[Nmax], s[Nmax], o, aux ;

int i,n,a,b,h,ls,ld,N,poz ; 
double lungime, latime, Arie, d ; 

int cmp ( punct a, punct b)
{
	if( a.panta == b.panta ) return a.x < b.x;
	
	return a.panta < b.panta;
}

int convex ()
{
	punct a,b,c;
	ll S;
	
	a=s[N-1]; b=s[N]; c=v[i];
	
	S = ( a.x - c.x ) * ( b.y - a.y ) + ( a.x - b.x ) * ( a.y - c.y ) ;
	
	return ( S > 0 ); 
}

int next ( int i )
{
	if( i < N ) return i + 1 ; 
	return 1 ;
}

int prev ( int i ) 
{
	if ( i > 1 ) return i - 1 ;
	return N ;
}

int semn( int a, int b, int c, int d )
{
	punct ab,cd ; 
	
	ab.x = s[b].x - s[a].x ;
	ab.y = s[b].y - s[a].y ; 
	
	cd.x = s[d].x - s[c].x ;
	cd.y = s[d].y - s[c].y ; 
	
	ll S = ab.x * cd.x + ab.y * cd.y ; 
	
	if( S >= 0 ) return 1 ;
	return -1 ;
}

double dist ( int i, int j )
{
	double a = s[i].x - s[j].x ;
	double b = s[i].y - s[j].y ;
	
	return sqrt( a*a + b*b );
}

double pdist ( int i, int p, int q ) 
{
	if( s[p].x == s[q].x ) 
		return (double)abs( s[i].x - s[p].x );
	
	if( s[p].y == s[q].y )
		return (double)abs(s[i].y - s[p].y ) ;
	
	double a =  s[q].y - s[p].y ;
	double b =  s[p].x - s[q].x ; 
	double c =  s[p].x * a + s[p].y * b ;
	
	return fabs( a * s[i].x + b * s[i].y - c ) / sqrt( a*a + b*b ) ; 
}

double Lungime ( int a, int b, int ls, int ld )
{
	double d = dist(a,b) ; 
	double x = dist(ls,a);
	double y = dist(b,ld);
	double X = pdist(ls,a,b);
	double Y = pdist(ld,a,b);
	
	return d + sqrt( x*x - X*X ) + sqrt( y*y - Y*Y ) ;
}
	
int main()
{
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	
	
	scanf("%d",&n);
	
	o.x = o.y = Inf ;
	Arie = Inf ;
	
	for( i = 1 ; i <= n ; i++ )
	{
		scanf("%lld %lld",&v[i].x,&v[i].y);
		
		if( v[i].x < o.x || v[i].x == o.x && v[i].y < o.y ) 
			o = v[i], poz = i ; 
	}
	
	aux = v[1] ; v[1] = v[poz] ; v[poz] = aux ;
	
	for( i = 2 ; i <= n ; i++ )
		v[i].panta = (double)( v[i].y - o.y ) / ( v[i].x - o.x ) ;	
	
	sort(v+2,v+n+1,cmp);
	
	s[1] = v[1] ; s[2] = v[2] ; N = 2 ; 
	
	for( i = 3 ; i <= n ; i++ )
	{
		while( !convex() && N > 2 ) N--;
		s[++N] = v[i] ;
	}
	
	if( N < 3 ) { printf("0.00"); return 0 ; }
	
	for( i = 1 ; i <= N ; i++ )
	{
		a = i ; 
		b = next(i) ; 
		
		ls = a ;  if( semn ( a, prev(a), a, b ) < 0 ) ls = prev(a) ;
		ld = b ;  if( semn ( a, b, b, next(b) ) > 0 ) ld = next(b) ; 
		
		lungime = Lungime( a, b, ls, ld ) ; 
		
		latime = 0 ;
		
		for( h = 1 ; h <= N ; h++ )
		{
			if( h == a || h == b ) continue ;
			d = pdist(h,a,b);
			if( d > latime ) 
				latime = d ;
		}
		
		if( lungime * latime < Arie ) 
			Arie = lungime * latime ;
	}
	
	printf("%.2lf",Arie);
	
	return 0 ; 
}