Cod sursa(job #594664)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 8 iunie 2011 18:59:55
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>

#define maxN 100005
#define INF (1LL<<60)
#define eps 1e-10

using namespace std;

FILE*f=fopen("rubarba.in","r");
FILE*g=fopen("rubarba.out","w");

int n,i,j,xmin,ymin = 1<<30,pctmin;
double ctg1,ctg2,d,Distmax,Distmin,m; int vf,a,b; long long c;
double a2,b2,c2,aria,best = INF;

struct pct{
	int x;
	int y;
	double ctg;
}A[maxN],aux,St[maxN];

inline double modul ( double j ){
	if ( j < 0 )
		return -j;
	return j;
}

struct cmp{
	inline bool operator () ( const pct &a , const pct &b ) {
		if ( modul(a.ctg - b.ctg) > eps )
			return a.ctg > b.ctg;
		if ( a.y == b.y )
			return a.x < b.x;
		return a.y > b.y;
	}
};

inline bool det ( pct a, pct b , pct c ){
	double Det = 1LL*(a.x - c.x) * (b.y - c.y) + 1LL*(a.y - c.y) * (c.x - b.x);
	if ( Det <= 0 )
		return 1;
	return 0;
}

inline double Dist ( pct x , double a , double b, double c ){
	double dst;
	dst = a * x.x + b * x.y + c;
	dst = dst / sqrt(1LL*a*a + 1LL*b*b);
	return dst;
}

inline void citire () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
		if ( A[i].y < ymin ){
			ymin = A[i].y; xmin = A[i].x ; pctmin = i;
		}
	}
}

inline void infasuratoare () {
	
	for ( i = 1 ; i <= n ; ++i ){
		A[i].x -= xmin ; A[i].y -= ymin;
		A[i].ctg = (double)A[i].x / A[i].y; 
	}
	aux = A[pctmin]; A[pctmin] = A[1]; A[1] = aux;
	
	sort( A+2, A+n+1, cmp() );
	
	for ( i = 1 ; i <= n ; ++i ){
		while ( vf > 1 && det(St[vf-1],St[vf],A[i]) ){
			--vf;
		}
		St[++vf] = A[i];
	}
	
	while ( det(St[1],St[vf-1],St[vf] ) && vf > 1 )
		St[vf].x = St[vf].y = St[vf].ctg = 0 , --vf;
	
	for ( i = 1 ; i <= vf ; ++i ){
		St[i].x += xmin; St[i].y += ymin;
	}
	St[vf+1] = St[1];
}

inline void solve () {
	
	
	for ( i = 1 ; i <= vf ; ++i ){
		a = St[i+1].y - St[i].y; b = St[i].x - St[i+1].x; c = 1LL*St[i+1].x * St[i].y - 1LL*St[i].x * St[i+1].y;
		Distmax = 0;
		
		for ( j = 1 ; j <= vf ; ++j ){
			if ( ( d = modul(Dist(St[j],a,b,c)) ) > Distmax ){
				Distmax = d;
			}
		}
		aria = Distmax;
		
		Distmin = INF; Distmax = -INF;
		if ( St[i+1].y != St[i].y ){
			m = (double)(St[i].x-St[i+1].x) / (St[i+1].y-St[i].y);
			a2 = m; b2 = -1; c2 = -m * St[1].x + St[1].y;
		}
		else{
			a2 = 1; b2 = 0; c2 = -St[i].x;
		}
		
		for ( j = 1 ; j <= vf ; ++j ){
			if ( ( d = Dist(St[j],a2,b2,c2) ) > Distmax ){
				Distmax = d;
			}
			if ( d < Distmin )
				Distmin = d;
		}
		
		aria = aria * ( Distmax - Distmin );
		
		if ( aria < best )
			best = aria;
	}
	
	if ( vf < 2 )
		best = 0.0;
	fprintf(g,"%.2lf\n",best);
}


int main () {
	
	citire();
	infasuratoare();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}