Cod sursa(job #483922)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 10 septembrie 2010 21:12:17
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <stdio.h>
#include <cmath>
#include <algorithm>
#define Nmax 100002
#define INF 10000000000000.0
#define D double
#define eps 0.000001

using namespace std;

struct punct{ D x,y; } P[Nmax],CL1,CL2,PI;
int semn_tg[Nmax],ind[Nmax],S[Nmax];
D xp,yp;
int N,p0;
punct pp0;
D arie_drept,A,B,C,AP,BP,CP,lat1,lat2[2];

inline D Dist_p(punct p1, punct p2){
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
inline int cmp(int i,int j){
	if( (P[i].y-yp)*(P[j].x-xp) == (P[i].x-xp)*(P[j].y-yp) )
		return P[i].x < P[j].x;
	return (P[i].y-yp)*(P[j].x-xp) < (P[i].x-xp)*(P[j].y-yp);
}
	
inline int semn(int p0,int p1,int p2){
	return (P[p1].x-P[p0].x)*(P[p2].y-P[p0].y) - (P[p2].x-P[p0].x)*(P[p1].y-P[p0].y) >0;
}

inline D Maxim( D x, D y ){ return x>y ? x:y; }
inline D Abs( D a ){
	return a>0 ? a:-a; 
}
inline D Distanta_dr(D A, D B, D C, punct p ){
	return abs(A*p.x+B*p.y+C)/sqrt(A*A+B*B);
}

int main(){
	int i,j,dcp;
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	scanf("%d",&N);
	xp=yp=INF;
	for(i=1;i<=N;++i){
		scanf("%lf%lf",&P[i].x,&P[i].y);
		if(P[i].x < xp || (P[i].x==xp && P[i].y<yp) ) 
			xp=P[i].x,yp=P[i].y,p0=i;
	}
	pp0.x=xp; pp0.y=yp;
	
	for(i=1;i<=N;++i)
		if( i!=p0 ){
			ind[++ind[0]]=i;
//			semn_tg[i]=( P[i].x-xp > 0 ? 1:-1)*( P[i].y-yp > 0 ? 1:-1);
		}
	sort(ind+1,ind+N,cmp);
	
	S[1]=p0; S[2]=ind[1]; S[0]=2;
	for(i=2;i<N;++i){
		while( S[0]>=2 && semn(S[S[0]-1],S[S[0]],ind[i]) <= 0 )
			-- S[0];
		S[++S[0]]=ind[i];
	}
	while( semn(S[1],S[S[0]-1],S[S[0]] ) <=0 ) 
		--S[0];
	
	S[++S[0]]=S[1]; arie_drept=INF;
	for(i=1;i<S[0];++i){
		if( P[S[i]].x != P[S[i+1]].x) 
			A=(P[S[i+1]].y-P[S[i]].y)/(P[S[i+1]].x-P[S[i]].x);
		else A=INF;
		B=-1;
		C=P[S[i]].y-A*P[S[i]].x;
		
		if( A!=0 )AP=-1/A; // dreapta perpendiculara
		else AP=INF;
		BP=-1;
		CP=P[S[i]].y-AP*P[S[i]].x;

		lat1=0; lat2[0]=lat2[1]=0;
		for(j=1;j<S[0];++j)
			if( S[j]!=S[i] && S[j]!=S[i+1] ){
				lat1=Maxim(lat1,Distanta_dr(A,B,C,P[S[j]]));
				
				dcp=AP*P[S[j]].x + BP*P[S[j]].y + CP>0;
				lat2[dcp]=Maxim(lat2[dcp],Distanta_dr(AP,BP,CP,P[S[j]]));
			}
		
		if( lat1 * ( lat2[0]+lat2[1] ) < arie_drept )
			arie_drept = lat1 * ( lat2[0]+lat2[1] );
	}
	
	printf("%.2lf\n",arie_drept);
	fclose(stdin); fclose(stdout);
	return 0;
}