Cod sursa(job #97826)

Utilizator stef2nStefan Istrate stef2n Data 9 noiembrie 2007 00:18:34
Problema Rubarba Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.46 kb
//#define DEBUG

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#ifdef DEBUG
#include <iostream>
#endif

#define EPS 1e-7
#define INF 1.e20
#define next(X) ((X+1)%H)
struct point
{
	int x, y;
	double u;
	bool operator != (point P)
	{
		return x!=P.x || y!=P.y;
	}
};

int N, H;
std::vector <point> P, Q;
int up, left, right;
double dist_up, dist_left, dist_right;
long double minArea=INF;

inline double distanta(double x1, double y1, double x2, double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

inline double unghi_polar(int x1, int y1, int x2, int y2)
{
	double cosinus=distanta(x2,y1,x1,y1)/distanta(x2,y2,x1,y1);
	if(x2>=x1)
		return acos(cosinus);
	else
		return M_PI-acos(cosinus);
}

inline char sign(point A, point B, point C)
{
	long long det = (long long)A.x*(B.y-C.y) - (long long)B.x*(A.y-C.y) + (long long)C.x*(A.y-B.y);
	return det==0 ? '0' : (det<0 ? '-' : '+');
}

inline char sign_d(double x1, double y1, double x2, double y2, double x3, double y3)
{
	long double det=x1*(y2-y3)-x2*(y1-y3)+x3*(y1-y2);
	return fabs(det)<EPS ? '0' : (det<0 ? '-' : '+');
}

inline bool cmp(point A, point B)
{
	if(fabs(A.u-B.u)<EPS)
		return distanta(P[0].x,P[0].y,A.x,A.y)>distanta(P[0].x,P[0].y,B.x,B.y);
	else
		return A.u<B.u;
}

void read_data()
{
	point aux;
	scanf("%d",&N);
	for(int i=0; i<N; i++)
	{
		scanf("%d %d",&aux.x,&aux.y);
		P.push_back(aux);
	}
}

void convex_hull()
{
	int i, poz=0;
	point aux;
	for(i=1; i<N; ++i)
		if(P[i].y<P[poz].y || (P[i].y==P[poz].y && P[i].x<P[poz].x))
			poz=i;
	aux=P[0];
	P[0]=P[poz];
	P[poz]=aux;

	for(i=1; i<N; i++)
		P[i].u=unghi_polar(P[0].x,P[0].y,P[i].x,P[i].y);
	sort(P.begin()+1,P.end(),cmp);
	P.push_back(P[0]);

	Q.push_back(P[0]);
	Q.push_back(P[1]);
	i=2;
	while(i<N && fabs(P[i].u-P[i-1].u)<EPS)
		++i;
	for(; i<=N; ++i)
		switch(sign(Q[Q.size()-2],Q.back(),P[i]))
		{
			case '+':
				Q.push_back(P[i]);
				break;
			default:
				Q.pop_back();
				--i;
				break;
		}
	Q.pop_back();
	H=Q.size();
}

inline double find_up(point A, double a, double b, double c)
{
	return fabsl((long double)a*A.x+(long double)b*A.y+c)/sqrtl((long double)a*a+(long double)b*b);
}

inline double find_left(point A, long double a, long double b, long double c, point B)
{
	double x, y;
	y = (a*a*A.y - a*b*A.x - b*c) / (a*a+b*b);
	x = a*(y-A.y)/b + A.x;
	if(sign_d(A.x,A.y,x,y,B.x,B.y)=='+' || (fabs(B.x-x)<EPS && fabs(B.y-y)<EPS))
		return distanta(x,y,B.x,B.y);
	else
		return -INF;
}

inline double find_right(point A, long double a, long double b, long double c, point B)
{
	double x, y;
	y = (a*a*A.y - a*b*A.x - b*c) / (a*a+b*b);
	x = a*(y-A.y)/b + A.x;
	if(sign_d(A.x,A.y,x,y,B.x,B.y)=='-' || (fabs(B.x-x)<EPS && fabs(B.y-y)<EPS))
		return distanta(x,y,B.x,B.y);
	else
		return -INF;
}

void find_up_left_right()
{
	up=left=0;
	right=1;
	dist_up=dist_left=0.;
	dist_right=distanta(Q[0].x,Q[0].y,Q[1].x,Q[1].y);

	double a, b, c;
	a=Q[0].y-Q[1].y;
	b=Q[1].x-Q[0].x;
	c=(double)Q[0].x*Q[1].y-(double)Q[0].y*Q[1].x;

	for(int i=1; i<H; ++i)
	{
		if(dist_up<find_up(Q[i],a,b,c))
		{
			up=i;
			dist_up=find_up(Q[i],a,b,c);
		}
		if(dist_left<find_left(Q[i],a,b,c,Q[0]))
		{
			left=i;
			dist_left=find_left(Q[i],a,b,c,Q[0]);
		}
		if(dist_right<find_right(Q[i],a,b,c,Q[0]))
		{
			right=i;
			dist_right=find_right(Q[i],a,b,c,Q[0]);
		}
	}
}

void try_edge(point A, point B)
{
	double a, b, c;
	a=A.y-B.y;
	b=B.x-A.x;
	c=(double)A.x*B.y-(double)A.y*B.x;

	dist_up=find_up(Q[up],a,b,c);
	dist_left=find_left(Q[left],a,b,c,A);
	dist_right=find_right(Q[right],a,b,c,A);

	while(dist_up<find_up(Q[next(up)],a,b,c) || dist_up==-INF)
	{
		up=next(up);
		dist_up=find_up(Q[up],a,b,c);
	}
	while(dist_left<find_left(Q[next(left)],a,b,c,A)|| dist_left==-INF)
	{
		left=next(left);
		dist_left=find_left(Q[left],a,b,c,A);
	}
	while(dist_right<find_right(Q[next(right)],a,b,c,A) || dist_right==-INF)
	{
		right=next(right);
		dist_right=find_right(Q[right],a,b,c,A);
	}
	if(minArea>(long double)dist_up*((long double)dist_left+(long double)dist_right))
		minArea=(long double)dist_up*((long double)dist_left+(long double)dist_right);
}


int main()
{
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	read_data();
	convex_hull();
#ifdef DEBUG
	std::cerr<<"Infasuratoarea convexa:"<<std::endl;
	for(std::vector<point>::iterator it=Q.begin(); it!=Q.end(); ++it)
		std::cerr<<"("<<it->x<<","<<it->y<<") ";
	std::cerr<<std::endl;
#endif
	find_up_left_right();
	for(int i=0; i<H-1; i++)
		try_edge(Q[i],Q[i+1]);
	try_edge(Q[H-1],Q[0]);
	printf("%.2Lf\n",minArea);
	return 0;
}