Cod sursa(job #594486)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 7 iunie 2011 22:45:47
Problema Rubarba Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>

#define maxN 100005
#define INF (1<<29)
#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 = INF,pctmin;
double ctg1,ctg2,d,Distmax,Distmin,m; int vf,a,b,c;
double a2,b2,c2,aria,best = INF;

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

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 = (a.x - c.x) * (b.y - c.y) + (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 = modul( a * x.x + b * x.y + c );
	dst = dst / sqrt(a*a + 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] ) )
		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 () {
	
	pctinf.x = -1000005; pctinf.y = -1000005;
	
	for ( i = 1 ; i <= vf ; ++i ){
		a = St[i+1].y - St[i].y; b = St[i].x - St[i+1].x; c = St[i+1].x * St[i].y - St[i].x * St[i+1].y;
		Distmax = 0;
		
		for ( j = 1 ; j <= vf ; ++j ){
			if ( ( d = Dist(St[j],a,b,c) ) > Distmax ){
				Distmax = d;
			}
		}
		aria = Distmax;
		
		if ( St[i+1].y == St[i].y ){
			a2 = 0; b2 = -2; c2 = -2;
		}
		else{
			if ( St[i+1].x == St[i].x ){
				a2 = 2; b2 = 0; c2 = 2;
			}
			else{
				m = (double)(St[i].x - St[i+1].x) / (St[i+1].y - St[i].y );
				a2 = m; b2 = -1; c2 = pctinf.y - m * pctinf.x;
			}
		}
		
		Distmax = 0; Distmin = INF;
		
		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;
	}
	
	fprintf(g,"%.2lf\n",best);
}


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