fo.cpp

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
 
using namespace std;
 
#define DEBUG(x) cout << ">>> " << #x << " : " << x << endl;
#define REP(i,a) for (int i = 0; i < (a); ++i)
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define FORD(i,a,b) for (int i = (a); i >= (b); --i)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
 
typedef long long ll;
 
 
struct Vector {
	Vector(double x_, double y_): x(x_), y(y_) {}
	double x, y;
	bool operator < (const Vector& o) const {
		if (x != o.x) return x < o.x;
		return y < o.y;
	}
	Vector operator - (const Vector& o) const {
		return Vector(x-o.x, y-o.y);
	}
	double size() const {
		return sqrt(x*x+y*y);
	}
};
 
double cross_product(Vector v1, Vector v2) {
	return v1.x*v2.y - v1.y*v2.x;
}
 
double direction(Vector segment1, Vector segment2, Vector point) {
	return cross_product(point-segment1, segment2-segment1);
}
 
void convex_hull(vector<Vector>& points, vector<Vector>& hull) {
	sort(points.begin(), points.end());
	vector<Vector> top, bot;
	REP(i, (int)points.size()) {
		while (top.size() >= 2 && direction(top[top.size()-2], points[i], top[top.size()-1]) <= 0) {
			top.pop_back();
		}
		top.push_back(points[i]);
		while (bot.size() >= 2 && direction(bot[bot.size()-2], points[i], bot[bot.size()-1]) >= 0) {
			bot.pop_back();
		}
		bot.push_back(points[i]);
	}
	reverse(bot.begin(), bot.end());
	hull = top;
	if (bot.size() > 2) {
		hull.insert(hull.end(), bot.begin()+1, bot.end()-1);
	}
}
 
int N;
vector<Vector> points;
vector<Vector> hull;
 
bool canImprove(int last, Vector base, Vector dir) {
	double score = cross_product(hull[last]-base, dir);
	int next = last+1;
	if (next == (int)hull.size()) next = 0;
	double opt = cross_product(hull[next]-base, dir);
	return opt > score;
}
 
int main() {
	while (scanf("%d", &N) == 1) {
		double best = 1.0/0.0;
		points.clear();
		hull.clear();
		int x, y;
		REP(i,N) {
			scanf("%d%d", &x, &y);
			points.push_back(Vector(x, y));
		}
		convex_hull(points, hull);
		int lastLeft = 0, lastTop = 0, lastRight = 0;
		double leftScore = 0, topScore = 0, rightScore = 0;
		Vector baseVec = hull[1] - hull[0];
		Vector perpVec(baseVec.y, -baseVec.x);
		REP(i, (int)hull.size()) {
			double opt = cross_product(hull[i]-hull[0], baseVec);
			if (opt < topScore) {
				lastTop = i;
				topScore = opt;
			}
			opt = cross_product(hull[i]-hull[0], perpVec);
			if (opt > leftScore) {
				lastLeft = i;
				leftScore = opt;
			}
			if (opt < rightScore) {
				lastRight = i;
				rightScore = opt;
			}
		}
		REP(base1, (int)hull.size()) {
			int base2 = base1+1;
			if (base2 == (int)hull.size()) base2 = 0;
			Vector baseVec = hull[base2] - hull[base1];
			Vector perpVec(baseVec.y, -baseVec.x);
			while (canImprove(lastTop, hull[base1], Vector(0,0) - baseVec)) {
				++lastTop;
				if (lastTop == (int)hull.size()) lastTop = 0;
			}
			while (canImprove(lastLeft, hull[base1], perpVec)) {
				++lastLeft;
				if (lastLeft == (int)hull.size()) lastLeft = 0;
			}
			while (canImprove(lastRight, hull[base1], Vector(0,0)-perpVec)) {
				++lastRight;
				if (lastRight == (int)hull.size()) lastRight = 0;
			}
			topScore = cross_product(hull[lastTop]-hull[base1], baseVec);
			leftScore = cross_product(hull[lastLeft]-hull[base1], perpVec);
			rightScore = cross_product(hull[lastRight]-hull[base1], perpVec);
			double baseSize = baseVec.size();
			topScore /= baseSize; leftScore /= baseSize; rightScore /= baseSize;
			//DEBUG(leftScore);
			//DEBUG(rightScore);
			//DEBUG(topScore);
			double total = 2*(leftScore - rightScore) - 2*topScore;
			if (total < best) best = total;
			//DEBUG(total);
		}
		printf("%lf\n", best);
	}
	return 0;
}