Cod sursa(job #247335)

Utilizator CezarMocanCezar Mocan CezarMocan Data 22 ianuarie 2009 20:22:00
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#define inf 1000000000000000.0

using namespace std;

struct punct {
	double x, y;
};
int nr, i, j, vf;
punct st[100100], v[100100], t;
double a, b, c, n, m, rez;

double det(punct a, punct b, punct c) {
	return (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y);
}

/*bool cmp(punct a, punct b) {
	if ((a.y - t.y) * (b.x - t.x) > (a.x - t.x) * (b.y - t.y))
		return true;
	else
		return false;
}*/

bool cmp(punct a, punct b){
	if ((a.y==a.x)&&(a.y==0))
		return true;
	
	if ((b.y==b.x)&&(b.y==0))
		return false;
	
	if (a.y*b.x==a.x*b.y)
		if (a.x<b.x)
			return true;
		else
			return false;
                
    if (a.y*b.x<=a.x*b.y)
        return true;
    else
        return false;
}


void convex_hull() {
	vf = 2;
	st[1] = v[1];
	st[2] = v[2];
	for (i = 3; i <= nr; i++) {
		while ((det(v[i], st[vf], st[vf - 1]) > 0) && (vf > 1))
			vf--;
		vf++;
		st[vf] = v[i];
	}
	
	while (det(st[2], st[1], st[vf]) > 0)
		vf--;
	
	vf++;
	st[vf] = st[1];
}

//Distanta Punct Dreapta
double dpd(double a, double b, double c, punct t) {
	return (fabs(a * t.x + b * t.y + c) / sqrt(a * a + b * b));
}

void solve() {
	punct p1, p2, p3;
	double mx, a1, b1, c1, m1, n1, l1, l2;
	int i, j, k;
	for (i = 1; i < vf; i++) {
		//am dreapta formata din punctele i si i + 1 de pe infasuratoare :)
		p1 = st[i]; p2 = st[i + 1];
		
		//panta
		if (p2.x == p1.x)
			a = m = inf;
		else
			a = m = (p2.y - p1.y) / (p2.x - p1.x);
		c = n = p1.y - m * p1.x;
		b = -1;
		mx = 0;
		for (j = 1; j < vf; j++)
			if (dpd(a, b, c, st[j]) > mx) {
				mx = dpd(a, b, c, st[j]);
				p3 = st[j];
			}
		l1 = mx;
		//printf("%lf %lf   %lf %lf  %lf %lf\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
		
		mx = 0;
		if (m == 0)
			a1 = m1 = -inf;
		else 
			a1 = m1 = -1.0 / m;
		b1 = -1;
		for (j = 1; j < vf; j++) 
			if (j != i && j != i + 1) {
				c1 = n1 = v[j].y - m1 * v[j].x;
				for (k = 1; k < vf; k++)
					if (k != j)
						if (dpd(a1, b1, c1, st[k]) > mx)
							mx = dpd(a1, b1, c1, st[k]);
			}
		l2 = mx;
		
		if (l1 * l2 < rez)
			rez = l1 * l2;
	}
}

int main() {
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out", "w", stdout);
	
	scanf("%d", &nr);
	for (i = 1; i <= nr; i++)
		scanf("%lf%lf", &v[i].x, &v[i].y);
	
	t = v[1];
	for (i = 2; i <= nr; i++)
		if ((v[i].x < t.x) || (v[i].x == t.x && v[i].y < t.y))
			t = v[i];
	
	for (i = 1; i <= nr; i++) {
		v[i].x -= t.x;
		v[i].y -= t.y;
	}
	sort(v + 1, v + nr + 1, cmp);
	for (i = 1; i <= nr; i++) {
		v[i].x += t.x;
		v[i].y += t.y;
	}	
	convex_hull();
/*	for (i = 1; i <= vf; i++)
		printf("%lf %lf\n", st[i].x, st[i].y);*/
	rez = inf;
	solve();
	
	printf("%.2lf\n", rez);
	
	return 0;
}