// Method: Rotating calipers. Comments at the end.
#include <algorithm>
#include <stdio.h>
#define MAX_N 100'000
typedef struct {
int x, y;
} point;
point p[MAX_N];
int n;
int st[MAX_N], ss; // Stack for Graham's scan.
long double min(long double x, long double y) {
return (x < y) ? x : y;
}
// Cross product p[a]p[b] · p[c]p[d].
long long dot4(int a, int b, int c, int d) {
return
(long long)(p[b].x - p[a].x) * (p[d].x - p[c].x) +
(long long)(p[b].y - p[a].y) * (p[d].y - p[c].y);
}
// Cross product p[a]p[b] · p[a]p[c]
long long dot(int a, int b, int c) {
return dot4(a, b, a, c);
}
// Signed area. This one uses points, not indices because cmp() calls it.
long long area(point a, point b, point c) {
return
(long long)(b.x - a.x) * (c.y - b.y) -
(long long)(b.y - a.y) * (c.x - b.x);
}
// Square of the Euclidean distance.
long long dist2(point a, point b) {
return
(long long)(a.x - b.x) * (a.x - b.x) +
(long long)(a.y - b.y) * (a.y - b.y);
}
bool cmp(point a, point b) {
long long d = area(p[0], a, b);
if (d == 0) {
// a and b are collinear with p[0]. Put the furthest one first.
return dist2(a, p[0]) > dist2(b, p[0]);
} else {
return d > 0;
}
}
// Brings the point having the minimum y coordinate in first position.
// Sorts the other points in polar order with respect to the first.
void polar_sort() {
// Minimum x as tiebreaker.
int min = 0;
for (int i = 1; i < n; i++) {
if ((p[i].y < p[min].y) || (p[i].y == p[min].y && p[i].x < p[min].x)) {
min = i;
}
}
point tmp = p[0];
p[0] = p[min];
p[min] = tmp;
std::sort(p + 1, p + n, cmp);
}
// Graham's scan convex hull algorithm.
void graham_scan() {
st[0] = 0;
st[1] = 1;
ss = 2;
for (int i = 2; i < n; i++) {
// Ignore points on the same ray as the previous point. Since the previous
// point was further away, the current one won't help.
if (area(p[0], p[st[ss - 1]], p[i]) != 0) {
while (area(p[st[ss - 2]], p[st[ss - 1]], p[i]) <= 0) {
ss--;
}
st[ss++] = i;
}
}
// Collect the points on the hull in ccw order.
for (int i = 0; i < ss; i++) {
p[i] = p[st[i]];
}
n = ss;
}
// Returns the next point in circular fashion.
int next(int k) {
return (k == n - 1) ? 0 : (k + 1);
}
long double rectangle_area(int b1, int b2, int r, int a, int l) {
// Note: this is rational. Probably not worth the effort, though.
return (long double)dot4(b1, b2, l, r)
/ dist2(p[b1], p[b2])
* area(p[b1], p[b2], p[a]);
}
long double rotating_calipers() {
// Find the initial right, across and left points for the base P[0]P[1].
int r = 1, a, l;
while (dot(0, 1, next(r)) > dot(0, 1, r)) {
r = next(r);
}
a = r;
while (area(p[0], p[1], p[next(a)]) > area(p[0], p[1], p[a])) {
a = next(a);
}
l = a;
while (dot(0, 1, next(l)) < dot(0, 1, l)) {
l = next(l);
}
long double min_area = rectangle_area(0, 1, r, a, l);
// For a visual explanation of why this works, see
// https://www.youtube.com/watch?v=OaGvH450jRM
for (int i = 1; i < n; i++) {
int j = next(i);
while (dot(i, j, next(r)) > dot(i, j, r)) {
r = next(r);
}
a = r;
while (area(p[i], p[j], p[next(a)]) > area(p[i], p[j], p[a])) {
a = next(a);
}
l = a;
while (dot(i, j, next(l)) < dot(i, j, l)) {
l = next(l);
}
min_area = min(min_area, rectangle_area(i, j, r, a, l));
}
return min_area;
}
int main() {
// Read the input data.
FILE* f = fopen("rubarba.in", "r");
fscanf(f, "%d", &n);
for (int i = 0; i < n; i++) {
fscanf(f, "%d %d", &p[i].x, &p[i].y);
}
fclose(f);
long double result = 0;
if (n > 2) {
polar_sort();
graham_scan();
if (n > 2) {
result = rotating_calipers();
}
}
f = fopen("rubarba.out", "w");
fprintf(f, "%.2Lf\n", result);
fclose(f);
return 0;
}
// First, find the convex hull. Next, one of the sides of the hull must
// support the rectangle. Try every side one by one. For every side, determine
// the farthest point to the left, across and right. The smallest rectangle is
// bounded by these extremes.
//
// To find the initial points, say for the side p[0]p[1], notice that the
// rightmost point r maximizes the dot product p[0]p[1] · p[0]p[r]. Similarly
// for the leftmost point l. As for the point across, a, it maximizes the area
// of the triangle p[0]p[1]p[a].
//
// When advancing the support side from p[i]p[i + 1] to p[i + 1]p[i + 2], the
// points r, l and a also advance counterclockwise.
//
// Returns the area of the rectangle supported by b1b2 with extremes r
// (right), a (across) and l (left).
//
// Having determined i, j = i + 1, r, l and a, what is the area of the
// rectangle? The height of the rectangle is the distance from a to ij. But
// that's also area(triangle aij) / |ij|. The width of the rectangle is the
// vector r - l projected on the ij axis. But by definition that is (r - l) ·
// ij / |ij| (cross product).