Cod sursa(job #599266)

Utilizator ChallengeMurtaza Alexandru Challenge Data 28 iunie 2011 14:02:53
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

const char InFile[]="rubarba.in";
const char OutFile[]="rubarba.out";
const int MaxN=100111;
const double FINF=1.0e64;

ifstream fin(InFile);
ofstream fout(OutFile);

struct Vector2
{
	Vector2(double x=0, double y=0):x(x),y(y){}
	Vector2 operator- (Vector2 v)
	{
		return Vector2(x-v.x,y-v.y);
	}
	double operator* (Vector2 v)
	{
		return x*v.x+y*v.y;
	}
	void normalize()
	{
		double d=sqrt(x*x+y*y);
		if(d)
		{
			x/=d;
			y/=d;
		}
	}
	void rotate90()
	{
		double tx(x),ty(y);
		x=-ty;
		y=tx;
	}

	double x,y;
};

typedef Vector2 Point2D;

int N,S[MaxN];
Point2D p[MaxN];

inline double sqrdist(const Point2D &a, const Point2D &b)
{
	double dx=a.x-b.x;
	double dy=a.y-b.y;
	return dx*dx+dy*dy;
}

struct cmp
{
	inline bool operator() (const Point2D &a, const Point2D &b)
	{
		double left=(a.y-p[1].y)*(b.x-p[1].x);
		double right=(b.y-p[1].y)*(a.x-p[1].x);
		if(left==right)
		{
			return sqrdist(a,p[1])>sqrdist(b,p[1]);
		}
		return left<right;
	}
};

inline double det(Point2D &a, Point2D &b, Point2D &c)
{
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

inline int sgn(double x)
{
	if(x==0)
	{
		return 0;
	}
	if(x<0)
	{
		return -1;
	}
	return 1;
}

inline void convexhull()
{
	int ind=0;
	p[0].x=p[0].y=FINF;
	for(register int i=1;i<=N;++i)
	{
		if(p[i].y<p[ind].y)
		{
			ind=i;
		}
		else if(p[i].y==p[ind].y && p[i].x<p[ind].x)
		{
			ind=i;
		}
	}

	swap(p[1],p[ind]);
	sort(p+2,p+N+1,cmp());

	S[0]=2;
	S[1]=1;
	S[2]=2;

	for(register int i=3;i<=N;++i)
	{
		while(S[0]>=2 && sgn(det(p[S[S[0]-1]],p[S[S[0]]],p[i]))==-1)
		{
			--S[0];
		}
		S[++S[0]]=i;
	}
	while(S[0]>3 && sgn(det(p[S[S[0]-1]],p[S[S[0]]],p[1]))==0)
	{
		--S[0];
	}
	N=S[0];
	for(register int i=1;i<=S[0];++i)
	{
		p[i]=p[S[i]];
	}
}

inline int next(const int &index)
{
	if(index==N)
	{
		return 1;
	}
	return index+1;
}

inline double mera()
{
	double sol=FINF;
	for(register int i=1;i<=N;++i)
	{
		Vector2 dir=p[next(i)]-p[i];
		dir.normalize();
		Vector2 pdir=dir;
		pdir.rotate90();
		double minc=FINF,maxc=-FINF;
		double d=-FINF;
		for(register int j=1;j<=N;++j)
		{
			Vector2 pos=p[j]-p[i];
			double coord=dir*pos;
			minc=min(minc,coord);
			maxc=max(maxc,coord);
			d=max(d,abs(pdir*pos));
		}

		sol=min(sol,(maxc-minc)*d);
	}
	return sol;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
	}
	fin.close();

	convexhull();

	fout<<setprecision(2)<<fixed<<mera();
	fout.close();
	return 0;
}