Cod sursa(job #592705)

Utilizator crushackPopescu Silviu crushack Data 29 mai 2011 23:10:14
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define NMax 100010
using namespace std;

const char IN[]="rubarba.in",OUT[]="rubarba.out";

struct point{
	double x,y;
	bool operator<(point const &b) const{
		return x<b.x || x==b.x && y<b.y;
	}
} p[NMax] , H[NMax];

int N,L;
double Rez;

double cross(point const &a,point const &b,point const &c){
	return (1.* a.x*(b.y-c.y) + 1.* b.x*(c.y-a.y) + 1.* c.x*(a.y-b.y));
}

void convexHull()
{
	int i,l;
	L=0;
	sort(p,p+N);
	for (i=0;i<N;++i)
	{
		while ( L>1 && cross( H[L-1] , H[L-2] , p[i] )<=0)
			--L;
		H[L++]=p[i];
	}
	l=L;
	for (i=N-2;i>=0;--i)
	{
		while (L>l && cross( H[L-1] , H[L-2] , p[i] )<=0)
			--L;
		H[L++]=p[i];
	}
	--L;
}

inline double Arie(double d1,double d2){
	return d1*d2;
}

inline double sqr(double x){
	return x*x;
}

inline double dist(point a,point b){
	return sqrt(  sqr(a.x-b.x) + sqr(a.y-b.y));
}

inline double abs(double x){
	return x<0 ? -x : x;
}

inline double dist(point O,point a,point b){
	return abs(cross(O,a,b))/dist(a,b);
}

double dist2(point O,point a,point b,point c)
{
	if (a.y==b.y)
		return abs(O.x-c.x);
	double m=-(b.x-a.x)/(double)(b.y-a.y);
	double n=c.y - m*c.x;
	return abs((m*O.x -O.y + n)/(double)sqrt(1+m*m));
}

void solve()
{
	int p1,p2,p3,p4;
	double rt;
	
	p1=p2=0;
	
	while ( dist(H[p2],H[p1],H[(p1+1)%L]) <=dist(H[(p2+1)%L],H[p1],H[(p1+1)%L]))
		p2=(p2+1)%L;
	
	for (p3=0 ; dist2(H[p3] , H[p1],H[(p1+1)%L],H[p2]) <= dist2(H[(p3+1)%L] , H[p1],H[(p1+1)%L],H[p2]);)
		p3=(p3+1)%L;
	
	for (p4=p2 ; dist2(H[p4] , H[p1],H[(p1+1)%L],H[p2]) <= dist2(H[(p4+1)%L] , H[p1],H[(p1+1)%L],H[p2]) && p4!=p1;)
		p4=(p4+1)%L;
	
	//printf("%d\n%d\n%d\n%d\n",p1,p2,p3,p4);
	
	Rez=Arie( dist(H[p2],H[p1],H[(p1+1)%L]) ,
			  dist2(H[p3], H[p1],H[(p1+1)%L],H[p2])+ dist2(H[p4] , H[p1], H[(p1+1)%L] , H[p2]) );
	
	for (++p1;p1<L;++p1)
	{
		while ( dist(H[p2],H[p1],H[(p1+1)%L]) <=dist(H[(p2+1)%L],H[p1],H[(p1+1)%L])) 
		p2=(p2+1)%L;
		
		for (; dist2(H[p3] , H[p1],H[(p1+1)%L],H[p2]) <= dist2(H[(p3+1)%L] , H[p1],H[(p1+1)%L],H[p2]);)
			p3=(p3+1)%L;
	
		for (; dist2(H[p4] , H[p1],H[(p1+1)%L],H[p2]) <= dist2(H[(p4+1)%L] , H[p1],H[(p1+1)%L],H[p2]) && p4!=p1;)
			p4=(p4+1)%L;
		
		rt=Arie( dist(H[p2],H[p1],H[(p1+1)%L]) ,
			dist2(H[p3], H[p1],H[(p1+1)%L],H[p2])+ dist2(H[p4] , H[p1], H[(p1+1)%L] , H[p2]));
			
		//printf("%.2lf\n",rt);
			
		Rez= rt!=0 && rt<Rez ? rt : Rez;
	}
	
}

int main()
{
	int i;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=0;i<N;++i)
		scanf("%lf%lf",&p[i].x,&p[i].y);
	fclose(stdin);
	
	convexHull();
	if (L>2)
		solve();
	else
		Rez=0;
	
	freopen(OUT,"w",stdout);
	printf("%.4lf\n",Rez);
	fclose(stdout);
	
	return 0;
}