Cod sursa(job #596376)

Utilizator savimSerban Andrei Stan savim Data 16 iunie 2011 23:35:39
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX_N 100010

#define inf 100000000000000.0
#define VMAX 1000000

int n, m;

double sol = inf;

struct punct {
	double x, y;
} A[MAX_N], Hull[MAX_N];

inline bool cmp(const punct &P, const punct &Q) {
	return atan2(P.y - A[1].y, P.x - A[1].x) < atan2(Q.y - A[1].y, Q.x - A[1].x);
}

inline double det(const punct &A, const punct &B, const punct &C) {
	return 1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y - 
		   1LL * A.x * C.y - 1LL * B.x * A.y - 1LL * C.x * B.y; 
}

void get_hull() {
	int p = 1;

	for (int i = 2; i <= n; i++)
		if (A[i].x < A[p].x || (A[i].x == A[p].x && A[i].y < A[p].y))
			p = i;

	swap(A[1], A[p]);
	
	sort(A + 2, A + n + 1, cmp);

	Hull[1] = A[1]; Hull[2] = A[2]; m = 2;
	for (int i = 3; i <= n; i++) {
		//verific daca punctul curent este pe ultima latura a infasuratorii
		if (!(det(A[i], Hull[m], Hull[m - 1]) == 0 && min(Hull[m].x, Hull[m - 1].x) <= A[i].x && A[i].x <= max(Hull[m].x, Hull[m - 1].x))) 
    		Hull[++m] = A[i];

		while (m > 2 && det(Hull[m - 2], Hull[m - 1], Hull[m]) <= 0) {
    		swap(Hull[m - 1], Hull[m]);
			m--;
		}
	}

	n = m;
	for (int i = 1; i <= n; i++)
		A[i] = Hull[i];
}

inline double dist(punct A, punct B) {
	double ans = (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);

	return sqrt(ans);
}

inline double dist_line(punct A, punct B, double m) { //dreapta fata de care trebuie sa gasesc distanta are tangenta m si trece prin B
	//cazuri speciale: m = 0 sau m = inf

	if (m == 0)
		return fabs(A.y - B.y);

	if (m == inf)
		return fabs(A.x - B.x);

	double n = B.y - m * B.x;
	
	punct C;
	C.x = B.x + 1;
	C.y = C.x * m + n;

	double h = det(A, B, C) / dist(B, C);
	if (h < 0)
		h = -h;

	return h;
}

inline int next(int i) {
	return (i < n) ? (i + 1) : 1;
}

inline double inv(double m) {
	if (m == 0)
		return inf;
	if (m == inf)
		return 0;

	return -1.0 / m;
}

void solve() {
	get_hull();
	
	//algoritm O(n^2)

	for (int i = 1; i <= n; i++) {
    	int nxt = next(i);

		double m;
		if (A[i].x == A[nxt].x)
			m = inf;
		else
			m = 1.0 * (A[nxt].y - A[i].y) / (A[nxt].x - A[i].x);

		int left = i, up = i, right = i;

		//gasesc up si left
		for (int j = next(i); j != i; j = next(j)) {
			if (dist_line(A[j], A[i], m) > dist_line(A[up], A[i], m))
				up = j;
        	if (dist_line(A[j], A[i], inv(m)) > dist_line(A[left], A[i], inv(m)))
				left = j;
		}

		for (int j = next(left); j != left; j = next(j))
			if (dist_line(A[j], A[left], inv(m)) > dist_line(A[right], A[left], inv(m)))
				right = j;

		double current_sol = dist_line(A[up], A[i], m) * dist_line(A[left], A[right], inv(m));
		if (current_sol < sol)
			sol = current_sol;
	}

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

int main() {

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

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf %lf", &A[i].x, &A[i].y);

	solve();

	return 0;
}