#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;
const string file = "rubarba";
const string infile = file + ".in";
const string outfile = file + ".out";
struct Point
{
Point()
{
}
Point(int x, int y)
{
this->x = x;
this->y = y;
}
int x;
int y;
};
vector<Point> points;
vector<Point> convexHull;
int N;
double minArea;
long long CrossProduct(const Point& s, const Point& p1, const Point& p2)
{
long long result = 1LL * (p1.x - s.x)*(p2.y - s.y) - 1LL * (p1.y - s.y) * (p2.x - s.x);
return result;
}
Point Substract(const Point&a, const Point &b)
{
int px = b.x - a.x;
int py = b.y - a.y;
return Point(px, py);
}
double Distance(const Point&a)
{
return sqrt((double)(a.x * a.x) + a.y * a.y);
}
bool SortPredicate(const Point& a, const Point& b)
{
double val1 = 1.0*(a.y - points[0].y )/(1.0*a.x - points[0].x);
double val2 = 1.0*(b.y - points[0].y )/(1.0*b.x - points[0].x);
if(val1 < val2)
{
return true;
}
if(val1 > val2)
{
return false;
}
return Distance(Substract(a, points[0])) < Distance(Substract(b, points[0]));
}
void citire()
{
ifstream fin(infile.c_str());
fin >> N;
points.reserve(N);
int minI = 0;
for(int i = 0 ; i < N; i++)
{
int x, y;
fin >> x >> y;
points.push_back(Point(x, y));
if(points[minI].x > x)
{
minI = i;
}
else if(points[minI].x == x)
{
minI = points[minI].y > y ? i : minI;
}
}
swap(points[0], points[minI]);
fin.close();
}
void GrahamScan()
{
sort(points.begin() + 1, points.end(), SortPredicate);
for(int i = 0; i < N; i++)
{
while(convexHull.size() >= 2 && CrossProduct(convexHull[convexHull.size() - 2], convexHull[convexHull.size() - 1], points[i]) <= 0LL)
{
convexHull.pop_back();
}
convexHull.push_back(points[i]);
}
}
struct PointD
{
double x;
double y;
PointD()
{
}
PointD(double x, double y)
{
this->x = x;
this->y = y;
}
};
struct LineD
{
LineD()
{
}
LineD(const Point& p1, const Point& p2)
{
this->slope = 1.0 *(p2.y - p1.y) / (p2.x - p1.x);
this->c = p1.y - p1.x * slope;
}
LineD(const PointD& p1, double slope)
{
this->c = p1.y - p1.x * slope;
this->slope = slope;
}
LineD(const Point& p1, double slope)
{
this->c = p1.y - p1.x * slope;
this->slope = slope;
}
double slope;
double c;
};
double Distance(const LineD & line, const Point& p1 )
{
double s = p1.y - line.slope * p1.x - line.c;
return s / sqrt(1 + line.slope * line.slope);
}
double ProdusScalar(const PointD& p1, const PointD& p2)
{
return p1.x * p2.x + p1.y * p2.y;
}
double Norma(const PointD& p)
{
return sqrt(p.x * p.x + p.y * p.y);
}
PointD Translate(const PointD& p1, const PointD& p2)
{
return PointD(p2.x - p1.x, p2.y - p1.y);
}
void RotateClockwise(PointD& p, double sine, double cosine)
{
double x = p.x;
double y = p.y;
p.x = x * cosine + y * sine;
p.y = - x * sine + y * cosine;
}
int Next(int i)
{
return i == 0 ? convexHull.size() - 1 : i - 1;
}
int Prev(int i)
{
return i == convexHull.size() - 1 ? 0 : i + 1;
}
struct Calliper
{
int p;
PointD v;
bool marked;
double nextAngle;
void rotate(double sine, double cosine)
{
marked = false;
if(cosine == nextAngle)
{
marked = true;
p = Next(p);
}
RotateClockwise(v, sine, cosine);
}
double getNextAngle()
{
Point &p1 = convexHull[p];
Point &p2 = convexHull[Next(p)];
Point translated = Substract(p1, p2);
PointD t(translated.x, translated.y);
double ang = ProdusScalar(v, t) / Norma(t);
nextAngle = ang;
return ang;
}
};
Calliper cal[4];
void initCallipers()
{
int xMin = 0;
int xMax = 0;
int yMin = 0;
int yMax = 0;
for(unsigned int i = 0; i < convexHull.size(); i++)
{
int currentPoint = i;
xMin = convexHull[currentPoint].x < convexHull[xMin].x ? currentPoint : xMin;
xMax = convexHull[currentPoint].x > convexHull[xMax].x ? currentPoint : xMax;
yMin = convexHull[currentPoint].y < convexHull[yMin].y ? currentPoint : yMin;
yMax = convexHull[currentPoint].y > convexHull[yMax].y ? currentPoint : yMax;
}
double dXdif = (convexHull[xMax].x - convexHull[xMin].x);
double dYdif = (convexHull[yMax].y - convexHull[yMin].y);
minArea = dXdif * dYdif;
cal[0].v = PointD(0, 1); cal[0].p = xMin;
cal[1].v = PointD(0, -1); cal[1].p = xMax;
cal[2].v = PointD(-1, 0); cal[2].p = yMin;
cal[3].v = PointD(1, 0); cal[3].p = yMax;
}
const double INF = 10000000000000000000.00L;
double GetSlope(const Point& p1, const Point& p2)
{
if(p1.x == p2.x)
{
return INF;
}
return 1.0 * (p1.y - p2.y) / (p1.x - p2.x);
}
void CalculateArea()
{
LineD lines[2];
Point l[2];
for(int i = 0; i < 4; i++)
{
if(cal[i].marked == true)
{
l[0] = convexHull[cal[i].p];
l[1] = convexHull[Prev(cal[i].p)];
}
}
double slope1 = GetSlope(l[0], l[1]);
if(slope1 == INF || fabs(slope1) <= 0.000000001L ) return;
double slope2 = -1.0 / slope1;
lines[0] = LineD(l[0], slope1);
lines[1] = LineD(PointD((1.0 * l[0].x - l[1].x)/ 2.0, (1.0 * l[0].y - l[1].y)/ 2.0), slope2);
double up = 0;
double left = -INF;
double right = INF;
for(int i = 0; i < 4; i++)
{
double d;
d = fabs(Distance(lines[0], convexHull[cal[i].p]));
up = max(up, d);
d = Distance(lines[1], convexHull[cal[i].p]);
left = max(left, d);
right = min(right, d);
}
double area = 0;
area = up * (left - right);
minArea = min(area, minArea);
cout << fixed << setprecision(2) << "AREA =\t" << area << "\n\n";
}
void RotatingCallipers()
{
if(convexHull.size() <= 2)
{
minArea = 0;
return;
}
initCallipers();
PointD x(0, 1);
while(ProdusScalar(x, cal[0].v) >= -0.0001)
{
double minAngle = -1;
for(int i = 0; i < 4; i++)
{
minAngle = max(minAngle, cal[i].getNextAngle());
}
double sine = sqrt(1.0 - minAngle * minAngle);
for(int i = 0; i < 4; i++)
{
cal[i].rotate(sine, minAngle);
}
CalculateArea();
}
}
void solve()
{
GrahamScan();
RotatingCallipers();
}
void afisare()
{
ofstream fout(outfile.c_str());
fout << fixed << setprecision(2) << minArea << "\n";
fout.close();
}
int main()
{
citire();
solve();
afisare();
}