Cod sursa(job #597130)

Utilizator katakunaCazacu Alexandru katakuna Data 21 iunie 2011 11:19:47
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

#define Nmax 100010
#define LL long long
#define LD long double
#define INF (double) ((LL)1 << 30)

struct punct {
	int x, y;
};

punct P[Nmax], V[Nmax];
int n, N;

long double dist (int x, int y,long double tg, int x0, int y0) {
	                  
    if (tg == 0) return fabs (y - y0);
	if (tg == INF) return fabs (x - x0);

	long double A, B, C;
	A = tg; B = -1; C = (LD)y - tg * (LD)x;

	long double D = (A * (LD)x0 + B * (LD)y0 + C ) / sqrt ( A * A + B * B);

	return fabs(D); 
}

void rezolva () {
	
	int i, j, dr, sus, jos;
	long double tg, tg2, sol = INF, Ar;

	P[n+1] = P[1];
	for (i = 1; i <= N; i++) {
		
		if (V[i].x != V[i+1].x) {
			tg = (LD)(V[i+1].y - V[i].y) / (LD)(V[i+1].x - V[i].x); 
			if (tg != 0) tg2 = -1.0 / tg; 
			else tg2 = INF;
		}
		else {tg = INF; tg2 = 0;}

		dr = sus = i;

		j = i + 1;
		if (j == N + 1) j = 1;
		for (; j != i;) {
		
			if (dist (V[i].x, V[i].y, tg, V[j].x, V[j].y) > dist (V[i].x, V[i].y, tg, V[dr].x, V[dr].y) )
				dr = j;
			if (dist (V[i].x, V[i].y, tg2, V[j].x, V[j].y) > dist (V[i].x, V[i].y, tg2, V[sus].x, V[sus].y))
				sus = j;

			j++;
			if (j == N + 1) j = 1;
		} 

        j = sus + 1; jos = sus;
		if (j == N + 1) j = 1;
		for (; j != sus;) {
		
			if (dist (V[sus].x, V[sus].y, tg2, V[j].x, V[j].y) > dist (V[sus].x, V[sus].y, tg2, V[jos].x, V[jos].y))
				jos = j;

			j++;
			if (j == N + 1) j = 1;
		} 

		
		Ar = dist (V[sus].x, V[sus].y, tg2, V[jos].x, V[jos].y) * dist (V[i].x, V[i].y, tg, V[dr].x, V[dr].y);
		if (sol > Ar) sol = Ar;

 		// printf ("%d %d %d %d %lf\n", i, dr, sus, jos, Ar);
	}

	printf ("%.2Lf\n", sol);
}

bool determinant (long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
	
	long long A = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (A <= 0) return 1;
	return 0;
}

void infasuratoare () {
	
	int stp = 1, p;
	int S[Nmax], viz[Nmax];

	memset (viz, 0, sizeof (viz));

	S[1] = 1; S[2] = 2; viz[2] = 1; 
	N = 2; p = 2;
	while (!viz[1]) {
		
		while (viz[p] == 1) {
			p+= stp;
			if (p == n) 
				stp = -1;
		}

		while ( N >= 2 &&  determinant ( P[p].x, P[p].y, P[ S[N-1] ].x, P[ S[N-1] ].y, P[ S[N] ].x, P[ S[N] ].y ) ) {
			viz[ S[N] ] = 0;
			N--;
		}

		S[++N] = p;
		viz[p] = 1;
	}

	N--;
	int i;
	for (i = 1; i <= N; i++) {
		V[i] = P[ S[i] ];
		// printf ("%d %d\n", V[i].x, V[i].y);
	}
	//printf ("----------------------------\n");
}

bool cmp (const punct &a, const punct &b) {
	                                                                                              
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

void citire () {
	
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf ("%d %d", &P[i].x, &P[i].y);

	sort (P + 1, P + n + 1, cmp);
}

int main () {

	freopen ("rubarba.in", "r", stdin);
	freopen ("rubarba.out", "w", stdout);
	
	citire ();
	infasuratoare ();
	rezolva ();

	return 0;
}