Cod sursa(job #718465)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 20 martie 2012 20:24:39
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <cmath> 
#include <algorithm>
using namespace std;
#define nmax 100010
#define inf 10000000000000000000000LL
#define double long double

struct punct
{
	double x, y, m;
} v[nmax], st[2*nmax];
	
int n, l;
double sol;

int cmp (punct a, punct b)
{
	return a.m < b.m;
}

double semn (punct p1, punct p2, punct p3)
{
	double a = p1.y - p2.y;
	double b = p2.x - p1.x;
	double c = p1.x * p2.y - p2.x * p1.y;
	return a * p3.x + b * p3.y + c;
}

void infasuratoare()
{
	double yst = inf, xst = inf;
	int i, p=0, h=0; 
	for (i=1; i<=n; i++) 
		if (v[i].x < xst || (v[i].x == xst && v[i].y < yst))
		{
			yst = v[i].y; 
			xst = v[i].x;
			p = i;
		}
	for (i=1; i <= n; i++)
		if (i != p)
		{
			v[++h].x = v[i].x;
			v[h].y = v[i].y;
			if (v[i].x == xst) v[h].m = inf; else
			v[h].m = (v[i].y - yst) / (v[i].x - xst) ;
		}
	sort (v+1, v+n, cmp);
	h=1;
	st[1].x = xst;
	st[1].y = yst;
	
	for (i=1; i<n; i++)
	{
		while (h > 1 && semn (st[h-1], st[h], v[i])<0) h--;
		st[++h] = v[i];
	}
	l = h;
}

double dist (double x, double y, double a, double b, double c)
{
	double d =  a*x + b*y + c;
	d = d/ (sqrt (a*a + b*b));
	return d;
}

int main()
{
	freopen ("rubarba.in","r",stdin);
	freopen ("rubarba.out","w",stdout);
	scanf ("%d", &n);
	int i, j;
	double x, d1, d2, d3, a1, b1, c1, a2, b2, c2, m;
	for (i=1; i<=n; i++) scanf ("%lf %lf", &v[i].x, &v[i].y);
	
	infasuratoare();
	
	for (i=l+1; i<=l+l; i++) 
	{
		st[i].x = st[i-l].x;
		st[i].y = st[i-l].y;
	}
	sol = inf;
	for (i=1; i<l; i++)
	{
		if (st[i+1]. x == st[i].x) m = inf; else
		m = (st[i+1].y - st[i].y) / (st[i+1].x - st[i].x);
		c1 = st[i].y - m * st[i].x;
		a1 = m;
		b1 = -1;
		if (!m) m = inf; else
			m = - 1/m;
		a2 = m;
		c2 = (st[i].y + st[i+1].y)/2 - m * (st[i].x + st[i+1].x)/2;
		b2 = -1;
		d1 = d2 = d3 = 0;
		for (j = i; j<l+i; j++)
		{
			x = dist (st[j].x, st[j].y, a1, b1, c1);
			if (x < 0) x = -x;
			if (x > d1) d1 = x;
			x = dist (st[j].x, st[j].y, a2, b2, c2);
			if (x > d2)	d2 = x;
			if (x < d3) d3 = x;
		}
		if (1LL * (d2 - d3) * d1 < sol) sol = 1LL * (d2- d3) * d1;
	}
	printf("%.2Lf\n", sol);
}