Cod sursa(job #596184)

Utilizator savimSerban Andrei Stan savim Data 16 iunie 2011 13:42:41
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define MAX_N 100010

#define inf 1000000000

int n, m;

double sol = 100000000000000.0;

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();

	int right = 3, up = 3, left = 3;
	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);

//		printf("%.0lf %.0lf   %.0lf %.0lf   %lf\n", A[i].x, A[i].y, A[nxt].x, A[nxt].y, m);

		while (dist_line(A[up], A[i], m) <= dist_line(A[next(up)], A[i], m) && next(up) != i)
			up = next(up);

		while (dist_line(A[right], A[i], inv(m)) <= dist_line(A[next(right)], A[i], inv(m)) && right != up)
	        right = next(right);

		if (i == 1)
			left = up;

		while (dist_line(A[left], A[up], inv(m)) <= dist_line(A[next(left)], A[up], inv(m)) && next(left) != i)
			left = next(left);

//		printf("-> %.0lf %.0lf   %.0lf %.0lf   %.0lf %.0lf\n", A[right].x, A[right].y, A[up].x, A[up].y, A[left].x, A[left].y);

//		printf("%lf %lf\n\n", m, dist_line(A[up], A[i], m));

		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;
}