Cod sursa(job #670454)

Utilizator cont_de_testeCont Teste cont_de_teste Data 29 ianuarie 2012 11:37:01
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 100010
#define inf 0x3f3f3f3f
#define ll long long

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

inline int check (ll A, ll B) {
    if (B - A > 0) return -1;
    if (A - B > 0) return  1;
    return 0;
}

bool comp (const PR &A, const PR &B) {
    int X = check (A.x, B.x);
    if (X) return X < 0;
    return check (A.y, B.y) < 0;
}

inline int in (PR A, PR B, PR C) {
    return check (1LL * (A.y - B.y) * C.x + 1LL * (B.x - A.x) * C.y + (1LL * A.x * B.y) - (1LL * B.x * A.y), 0);
}

vector <int> H;
bool viz[MAX_N];

void convex (void) {
    sort (P + 1, P + n + 1, comp);
    H.push_back (1), H.push_back (2), viz[2] = 1;
    for (int i = 3, wh = 1; viz[1] == 0; H.push_back (i), viz[i] = 1) {
        for (; viz[i] ; i += wh = (i == n ? -1 : wh)) ;
        for (; H.size () > 1 && in (P[*(H.end () - 2)], P[H.back ()], P[i]) < 0; viz[H.back ()] = 0, H.pop_back ());
    }
}

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=1; 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(), v = H.size ();
for (i = 0; i < v; ++i)
printf ("%d %d\n", P[H[i]].x, P[H[i]].y);
	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;
}