// Method: Rotating calipers.
//
// First, find the convex hull. 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 as needed.
#include <algorithm>
#include <stdio.h>
const int MAX_N = 100'000;
const int UNKNOWN = -1;
struct point {
int x, y;
point operator - (const point& other) {
return { x - other.x, y - other.y };
}
};
point p[MAX_N];
int st[MAX_N]; // Stack for Graham's scan.
int n;
void read_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);
}
void find_min_y() {
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;
}
}
std::swap(p[0], p[min]);
}
long long dot(point a, point b) {
return (long long)a.x * b.x + (long long)a.y * b.y;
}
// Returns twice the area of ΔABC.
long long area2(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);
}
long long dist2(point a, point b) {
return dot(b - a, b - a);
}
void polar_sort() {
std::sort(p + 1, p + n, [](point a, point b) {
long long d = area2(p[0], a, b);
return (d > 0) ||
((d == 0) && (dist2(a, p[0]) < dist2(b, p[0])));
});
}
void graham_scan() {
int ss = 0;
for (int i = 0; i < n; i++) {
while ((ss >= 2) &&
(area2(p[st[ss - 2]], p[st[ss - 1]], p[i]) <= 0)) {
ss--;
}
st[ss++] = i;
}
// Collect the points on the hull in trigonometric order.
for (int i = 0; i < ss; i++) {
p[i] = p[st[i]];
}
n = ss;
}
int next(int k) {
return (k == n - 1) ? 0 : (k + 1);
}
// Returns the area of the rectangle supported by b1b2 with extremes r
// (right), a (across) and l (left).
//
// The height of the rectangle is the distance from a to b1b2. But that's also
// 2 * area(triangle ab1b2) / |b1b2|. The width of the rectangle is the vector
// r - l projected on the b1b2 axis. But by definition that is (r - l) · b1b2
// / |b1b2| (dot product). The rectangle's area is:
//
// [(r - l) · b1b2] * [2 * area(ab1b2)] / |b1b2|^2
long double rectangle_area(int b1, int b2, int r, int a, int l) {
return (long double)dot(p[b2] - p[b1], p[r] - p[l])
/ dist2(p[b1], p[b2])
* area2(p[b1], p[b2], p[a]);
}
void find_extremes(int b1, int& b2, int& r, int& a, int& l) {
b2 = next(b1);
point base = p[b2] - p[b1];
while (dot(base, p[next(r)] - p[b1]) > dot(base, p[r] - p[b1])) {
r = next(r);
}
while (area2(p[b1], p[b2], p[next(a)]) > area2(p[b1], p[b2], p[a])) {
a = next(a);
}
if (l == UNKNOWN) {
l = a;
}
while (dot(base, p[next(l)] - p[b1]) < dot(base, p[l] - p[b1])) {
l = next(l);
}
}
// For a visual explanation of why this works, see
// https://www.youtube.com/watch?v=OaGvH450jRM
long double rotating_calipers() {
int j, r = 1, a = 1, l = UNKNOWN;
long double min_area = 0;
for (int i = 0; i < n; i++) {
find_extremes(i, j, r, a, l);
long double area = rectangle_area(i, j, r, a, l);
if (!i || (area < min_area)) {
min_area = area;
}
}
return min_area;
}
long double find_min_area() {
find_min_y();
polar_sort();
graham_scan();
return (n <= 2) ? 0 : rotating_calipers();
}
void write_result(long double result) {
FILE* f = fopen("rubarba.out", "w");
fprintf(f, "%.2Lf\n", result);
fclose(f);
}
int main() {
read_data();
long double result = find_min_area();
write_result(result);
return 0;
}