Problem: Problem

Given a convex polygon consisting of $ N $ vertices.

When considering an equilateral triangle that includes all the vertices of the convex polygon, find the minimum value of the length of one side of the equilateral triangle.

Constraints

The input satisfies the following conditions.

* $ 3 \ le N \ le 10000 $
* $ -10 ^ 9 \ le px_i, py_i \ le 10 ^ 9 $
* No matter which of the three vertices of the convex polygon is selected, they do not exist on the same straight line.

Input

All inputs are given as integers in the following format:


$ N $
$ px_1 $ $ py_1 $
$ px_2 $ $ py_2 $
$ \ vdots $
$ px_N $ $ py_N $


The $ 1 $ line is given an integer $ N $ that represents the number of vertices of the convex polygon.
In the following $ N $ line, the information of each vertex of the convex polygon is given in the counterclockwise order.
In the $ 1 + i $ line, $ px_i $ and $ py_i $ representing the coordinates of the $ i $ th vertex are given separated by blanks.

Output

Output the minimum value of the length of one side of an equilateral triangle that satisfies the condition.
However, absolute or relative errors up to $ 10 ^ {-5} $ are acceptable.

Examples

Input

4
2 3
1 2
2 1
3 2


Output

3.04720672


Input

7
-96469 25422
-55204 -45592
-29140 -72981
98837 -86795
92303 63297
19059 96012
-67980 70342


Output

310622.35426197

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ld INF = (ld)10000000000;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-7;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;

//外心を求める。3点が同一直線上だとRE
LDP cent(LDP a[3]) {
	ld x[2], y[2];
	rep(i, 2) {
		x[i] = a[i + 1].first - a[0].first;
		y[i] = a[i + 1].second - a[0].second;
	}
	ld bunbo = 2 * (x[0] * y[1] - y[0] * x[1]);
	ld cx = (x[0] * x[0] * y[1] + y[0] * y[0] * y[1] - y[0] * x[1] * x[1] - y[0] * y[1] * y[1]) / bunbo;
	ld cy = (x[0] * x[1] * x[1] + x[0] * y[1] * y[1] - x[0] * x[0] * x[1] - y[0] * y[0] * x[1]) / bunbo;
	return { cx + a[0].first,cy + a[0].second };
}


bool eq(ld a, ld b) {
	return (abs(a - b) < eps);
}
//内積
ld dot(Point a, Point b) {
	return real(conj(a)*b);
}
//外積
ld cross(Point a, Point b) {
	return imag(conj(a)*b);
}
//線分
//直線にするなら十分通い２点を端点とすればよい
class Line {
public:
	Point a, b;
};
//円
class Circle {
public:
	Point p;
	ld r;
};
//3点の位置関係
int ccw(Point a, Point b, Point c) {
	b -= a; c -= a;
	if (cross(b, c) > eps)return 1;//a,b,cが反時計回り
	if (cross(b, c) < -eps)return -1;//a,b,cが時計回り
	if (dot(b, c) < 0)return 2;//c,a,bの順に一直線
	if (norm(b) < norm(c))return -2;//a,b,cの順に一直線
	return 0;//a,c,bの順に一直線
}
//2直線の交差判定
bool isis_ll(Line l, Line m) {
	return !eq(cross(l.b - l.a, m.b - m.a), 0);
}
//直線と線分の交差判定
bool isis_ls(Line l, Line s) {
	return (cross(l.b - l.a, s.a - l.a)*cross(l.b - l.a, s.b - l.a) < eps);
}
//点が直線上に存在するか
bool isis_lp(Line l, Point p) {
	return (abs(cross(l.b - p, l.a - p)) < eps);
}
//点が線分上に存在するか
bool isis_sp(Line s, Point p) {
	return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}
//線分と線分の交差判定
bool isis_ss(Line s, Line t) {
	if (isis_sp(s, t.a) || isis_sp(s, t.b) || isis_sp(t, s.a) || isis_sp(t, s.b))return true;
	return(cross(s.b - s.a, t.a - s.a)*cross(s.b - s.a, t.b - s.a) < -eps && cross(t.b - t.a, s.a - t.a)*cross(t.b - t.a, s.b - t.a) < -eps);
}
//点から直線への垂線の足
Point proj(Line l, Point p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}
//直線と直線の交点
//平行な２直線に対しては使うな！！！！
Point is_ll(Line s, Line t) {
	Point sv = s.b - s.a; Point tv = t.b - t.a;
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
//直線と点の距離
ld dist_lp(Line l, Point p) {
	return abs(p - proj(l, p));
}
//直線と直線の距離
ld dist_ll(Line l, Line m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}
//線分と直線の距離
ld dist_ls(Line l, Line s) {
	return isis_ls(l, s) ? 0 : min(dist_lp(l, s.a), dist_lp(l, s.b));
}
//線分と点の距離
ld dist_sp(Line s, Point p) {
	Point r = proj(s, p);
	return isis_sp(s, r) ? abs(p - r) : min(abs(p - s.a), abs(p - s.b));
}
//線分と線分の距離
ld dist_ss(Line s, Line t) {
	if (isis_ss(s, t))return 0;
	return min({ dist_sp(s,t.a),dist_sp(s,t.b),dist_sp(t,s.a),dist_sp(t,s.b) });
}

int n;
Point p[10001];
const ld th = pi / 3;
int main() {
	cout << fixed << setprecision(6);
	cin >> n;
	rep(i, n) {
		ld x, y; cin >> x >> y;
		p[i] = { x,y };
	}
	p[n] = p[0];
	ld out = INF;
	int l = 1, r = 1;
	rep(i, n) {
		Point d = p[i + 1] - p[i];
		Point d1 = d * Point{ cos(th),sin(th) };
		Point d2 = d * Point{ cos(-th),sin(-th) };
		Point x1 = p[i] + Point{ -INF * real(d1),-INF * imag(d1) };
		Point x2 = p[i] + Point{ INF * real(d1),INF * imag(d1) };
		Point y1 = p[i + 1] + Point{ -INF * real(d2),-INF * imag(d2) };
		Point y2 = p[i + 1] + Point{ INF*real(d2),INF*imag(d2) };
		Line l1 = { x1,x2 }, l2 = { y1,y2 };
		while (r!=i&&ccw(x1, p[r], x2) != -1) {
			r = (r + 1) % n;
		}
		while (r != i) {
			ld le = dist_lp(l1, p[r]);
			ld ri = dist_lp(l1, p[(r+1)%n]);
			if (le < ri)r = (r + 1) % n;
			else break;
		}
		ld ans = abs(p[i + 1] - p[i]);
		ans += max((ld)0,dist_lp(l1,p[r]) * 2 / sqrt(3.0));
		/*while (l != i + 1 && ccw(y1, p[l], y2) != -1) {
			l = (l - 1+n) % n;
		}*/
		if (l == i)l = (l + 1) % n;
		while (ccw(y1, p[(l + 1) % n],y2) == -1) {
			ld le = dist_lp(l2, p[l]);
			ld ri = dist_lp(l2, p[(l + 1) % n]);
			if (le < ri)l = (l + 1) % n;
			else break;
		}
		ans += max(ld(0),dist_lp(l2,p[l]) * 2 / sqrt(3.0));
		out = min(out, ans);
	}
	cout << out << endl;
	//stop
	return 0;
}