Cod sursa(job #182561)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 21 aprilie 2008 00:51:57
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAX_N 100010
#define inf 0x3f3f3f3f
#define ll long long

struct punct {
	int x, y;
	punct(int a, int b) { x=a, y=b; }
	punct() { x=y=0; }
	bool operator<(punct B) {
		return y<B.y || (y==B.y && x<B.x);
	}
} P[MAX_N];
int n, i, j;
int H[MAX_N], v;

struct comp {
	bool operator()(punct A, punct B) {
		long long x1 = (ll)A.x-P[0].x, x2 = (ll)B.x-P[0].x;
		long long y1 = (ll)A.y-P[0].y, y2 = (ll)B.y-P[0].y;
		if ( x1*y2==x2*y1 )
			return A<B;
		return x1*y2-x2*y1 > 0;
	}
};

bool test(punct A, punct B, punct C) {
	long long x1 = (ll)B.x-A.x, x2 = (ll)C.x-A.x;
	long long y1 = (ll)B.y-A.y, y2 = (ll)C.y-A.y;
	return x1*y2 - x2*y1 > 0;
}

void convex() {
	sort(P+1, P+n, comp());
	H[0] = 0, H[1] = 1, H[2] = 2, v=2;
	for ( i=3; i<n; ++i ) {
		while ( !test(P[H[v-1]], P[H[v]], P[i]) && v>=2 )
			--v;
		H[++v] = i;
	} 
	++v;
}

double myabs(double x) { return x<0?-x:x; }

int main() {
	freopen("rubarba.in", "r", stdin);
	freopen("rubarba.out", "w", stdout);

	scanf("%d", &n);
	int m = 0;
	for ( i=0; i<n; ++i ) {
		scanf("%d %d", &P[i].x, &P[i].y);
		if ( P[i]<P[m] ) m = i;
	}
	swap(P[m], P[0]);
	convex();

	H[v] = H[0];
	double Aria = 1./0;

	for ( i=0; i<v; ++i ) {
		double m1 = (1.*P[H[i+1]].y-P[H[i]].y)/(1.*P[H[i+1]].x-P[H[i]].x);
		double m2 = -1/m1;
		double c11 = 1./0, c12 = -1./0, c21 = 1./0, c22 = -1./0;
		double x, y;
		if ( myabs(m1) < 0.000001 || myabs(m2) < 0.000001 ) {
			for ( j=0; j<v; ++j ) {
				c11 = min(c11, 1.*P[H[j]].x); c12 = max(c12, 1.*P[H[j]].x);
				c21 = min(c21, 1.*P[H[j]].y); c22 = max(c22, 1.*P[H[j]].y);
			}
			x = c12-c11, y = c22-c21;
		} else {
			for ( j=0; j<v; ++j ) {
				double c1 = P[H[j]].y*1.-m1*P[H[j]].x;
				double c2 = P[H[j]].y*1.-m2*P[H[j]].x;
				c11 = min(c1, c11); c12 = max(c1, c12);
				c21	= min(c2, c21); c22 = max(c2, c22);
			}
			x = (c12-c11)/sqrt(1+1/(m1*m1));
			y = (c22-c21)/sqrt(1+1/(m2*m2));
		}
		double act = x*y;
		if ( act<Aria ) Aria = act;
	}
	printf("%.2lf\n", Aria);
	return 0;
}