Cod sursa(job #97756)

Utilizator stef2nStefan Istrate stef2n Data 8 noiembrie 2007 16:53:47
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
//#define DEBUG

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#ifdef DEBUG
#include <iostream>
#endif
using namespace std;

#define EPS 1e-7
#define INF 1.e20
#define NEXT(x) ((x+1)%H)
struct point{int x,y; double u;};

int N, H;
vector <point> P;
vector <point> Q;
double minArea=INF;
int Up, Left, Right;

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

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

void unghi_polar(point &P, const point Q)
{
	double cosinus=distance(P.x,Q.y,Q.x,Q.y)/distance(P.x,P.y,Q.x,Q.y);
	if(P.x>=Q.x)
		P.u=acos(cosinus);
	else
		P.u=M_PI-acos(cosinus);
}

bool cmp(point A, point B)
{
	return A.u<B.u;
}

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

void convex_hull()
{
	int i, min=0, p;
	point aux;

	for(i=1; i<N; i++)
		if(P[i].y<P[min].y || (P[i].y==P[min].y && P[i].x<P[min].x))
			min=i;
	aux=P[min];
	P[min]=P[0];
	P[0]=aux;
	P[0].u=-1.;

	for(i=1; i<N; i++)
		unghi_polar(P[i],P[0]);

	sort(P.begin(),P.end(),cmp);
	Q.push_back(P[0]);
	i=1;
	p=1;
	while(i<N-1 && fabs(P[i].u-P[i+1].u)<EPS)
	{
		i++;
		if(distance(P[0].x,P[0].y,P[p].x,P[p].y)<distance(P[0].x,P[0].y,P[i].x,P[i].y))
			p=i;
	}
	Q.push_back(P[p]);
	for(++i; i<N; ++i)
		switch(sign(Q[Q.size()-2],Q.back(),P[i]))
		{
			case '+':
				Q.push_back(P[i]);
				break;
			case '-':
				Q.pop_back();
				i--;
				break;
			case '0':
				if(distance(Q[Q.size()-2].x,Q[Q.size()-2].y,Q.back().x,Q.back().y) <
						distance(Q[Q.size()-2].x,Q[Q.size()-2].y,P[i].x,P[i].y))
					Q.back()=P[i];
				break;
		}
	H=Q.size();
#ifdef DEBUG
	cerr<<"Infasuratoarea convexa:"<<endl;
	for(vector <point> :: iterator it=Q.begin(); it!=Q.end(); ++it)
		cerr<<"("<<it->x<<","<<it->y<<") ";
	cerr<<endl;
#endif
}

int get_left()
{
	int p=0;
	for(int i=1; i<H; i++)
		if(Q[p].x>Q[i].x || (Q[p].x==Q[i].x && Q[p].y<Q[i].y))
			p=i;
	return p;
}

inline double dist_to_line(int x, int y, double a, double b, double c)
{
	return fabs(a*x+b*y+c)/sqrt(a*a+b*b);
}

inline double dist_horiz(double x0, double y0, double a, double b, double c, point A)
{
	double x, y;
	y = (a*a*y0 - a*b*x0 - b*c) / (a*a+b*b);
	x = a*(y-y0)/b + x0;
	return distance(x,y,A.x,A.y);
}

void try_edge(point A, point B)
{
	double a, b, c;
	a=A.y-B.y;
	b=B.x-A.x;
	c=A.x*B.y-A.y*B.x;
	while(dist_to_line(Q[Up].x,Q[Up].y,a,b,c)<dist_to_line(Q[NEXT(Up)].x,Q[NEXT(Up)].y,a,b,c))
		Up=NEXT(Up);
	while(dist_horiz(Q[Right].x,Q[Right].y,a,b,c,A)<dist_horiz(Q[NEXT(Right)].x,Q[NEXT(Right)].y,a,b,c,A))
		Right=NEXT(Right);
	while(dist_horiz(Q[Left].x,Q[Left].y,a,b,c,A)<dist_horiz(Q[NEXT(Left)].x,Q[NEXT(Left)].y,a,b,c,A))
		Left=NEXT(Left);
	double area=dist_to_line(Q[Up].x,Q[Up].y,a,b,c)*(dist_horiz(Q[Right].x,Q[Right].y,a,b,c,A)+dist_horiz(Q[Left].x,Q[Left].y,a,b,c,A));
	if(minArea>area)
		minArea=area;
}


int main()
{
	freopen("rubarba.in","r",stdin);
	freopen("rubarba.out","w",stdout);
	read_data();
	convex_hull();
	Up=1;
	Right=1;
	Left=get_left();
	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;
}