Pagini recente » Cod sursa (job #2909444) | Cod sursa (job #1893646) | Cod sursa (job #648040) | Cod sursa (job #165368) | Cod sursa (job #670485)
Cod sursa(job #670485)
# include <algorithm>
# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;
# define x first
# define y second
typedef long long ll;
typedef pair <int, int> VR;
const char *FIN = "rubarba.in", *FOU = "rubarba.out";
const int MAX = 100010;
VR V[MAX];
int N, sz;
inline int check (ll A, ll B) {
if (B - A > 0) return -1;
if (A - B > 0) return 1;
return 0;
}
bool comp (const VR &A, const VR &B) {
if (1LL * A.x * B.y == 1LL * B.x * A.y)
return A < B;
return 1LL * A.x * B.y > 1LL * B.x * A.y;
}
inline int in (VR A, VR B, VR 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> stk;
bool viz[MAX];
void convex_hull (void) {
sort (V + 1, V + N + 1, comp);
stk.push_back (1), stk.push_back (2), viz[2] = 1;
for (int i = 3, wh = 1; viz[1] == 0; stk.push_back (i), viz[i] = 1) {
for (; viz[i] ; i += wh = (i == N ? -1 : wh)) ;
for (; stk.size () > 1 && in (V[*(stk.end () - 2)], V[stk.back ()], V[i]) < 0; viz[stk.back ()] = 0, stk.pop_back ());
}
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d", &N);
for (int i = 1; i <= N; ++i)
scanf ("%d %d", &V[i].x, &V[i].y);
convex_hull (), sz = stk.size () - 1;
double oo = 99999999999999999999.0, sol = oo;
for (int i = 0; i < sz; ++i) {
double pant1 = (1.0 * V[stk[i + 1]].y - V[stk[i]].y) / (1.0 * V[stk[i + 1]].x - V[stk[i]].x), pant2 = -1 / pant1;
if (fabs (pant1) < 0.000001 || fabs (pant2) < 0.000001) {
double min1 = oo, min2 = oo, max1 = -oo, max2 = -oo;
for (int j = 0; j < sz; ++j) {
min1 = min (min1, 1.0 * V[stk[j]].x);
min2 = min (min2, 1.0 * V[stk[j]].y);
max1 = max (max1, 1.0 * V[stk[j]].x);
max2 = max (max2, 1.0 * V[stk[j]].y);
}
sol = min (sol, (max1 - min1) * (max2 - min2));
} else {
double min1 = oo, min2 = oo, max1 = -oo, max2 = -oo;
for (int j = 0; j < sz; ++j) {
min1 = min (min1, 1.0 * V[stk[j]].y - pant1 * V[stk[j]].x);
min2 = min (min2, 1.0 * V[stk[j]].y - pant2 * V[stk[j]].x);
max1 = max (max1, 1.0 * V[stk[j]].y - pant1 * V[stk[j]].x);
max2 = max (max2, 1.0 * V[stk[j]].y - pant2 * V[stk[j]].x);
}
sol = min (sol, ((max1 - min1) / sqrt (1 + 1 / (pant1 * pant1))) * ((max2 - min2) / sqrt (1 + 1 / (pant2 * pant2))));
}
}
fprintf (fopen (FOU, "w"), "%.2lf", sol);
}