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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007 
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define double long double


typedef complex<double> pt;
typedef pair<pt,pt> L;
typedef vector<P> poly;
const double EPS = 1e-9;
#define x real()
#define y imag()
bool eq(double a,double b){
  return (-EPS < a-b && a-b < EPS);
}
double dot(pt a,pt b){
	return (conj(a)*b).x;
}
double cross(pt a,pt b){
	return (conj(a)*b).y;
}
int ccw(pt a,pt b,pt c){
	b -= a; c -= a;
	if(cross(b,c) > EPS) return 1; // counter clockwise
	if(cross(b,c) < -EPS) return -1; // clockwise
	if(dot(b,c) < -EPS) return 2; //c-a-b
	if(norm(b) < norm(c)) return -2; //a-b-c
	return 0; //a-c-b
}
bool cmp(const pt& a,const pt& b){
	if(-EPS < a.x-b.x && a.x-b.x < EPS) return a.y < b.y;
	else return a.x < b.x;
}
vector<pt>convex_hull(vector<pt>ps)
{
	sort(ps.begin(),ps.end(),cmp);
	int k=0,n = ps.size();
	vector<pt>qs(n*2);
	for(int i=0;i<n;i++)
	{
		while(k>1 && ccw(qs[k-2],qs[k-1],ps[i]) == -1) k--;
		qs[k++] = ps[i];
	}
	for(int i=n-2,t=k;i>=0;i--)
	{
		while(k>t && ccw(qs[k-2],qs[k-1],ps[i]) == -1) k--;
		qs[k++] = ps[i];
	}
	qs.resize(k-1);
	return qs;
}
//平行?
bool is_par(pt a,pt b,pt c,pt d){
    b -= a; d -= c;
	if(abs(b.y*d.x - b.x*d.y) < EPS){
		return 1;
	}
	return 0;
}

//直線同士
pt crossPoint(pt a,pt b,pt c,pt d){
	double A = cross(b-a,d-c);
	double B = cross(b-a,b-c);
	if( fabs(A) < EPS && fabs(B) < EPS ) return c;
	else if(fabs(A) >= EPS ) return c+B/A*(d-c);
	else return pt(1e9,1e9);
}
//線分同士の交点
bool on_segment(pair<pt,pt> a,pt p){
  return eq(abs(a.first-a.second)-abs(a.first-p)-abs(a.second-p),0);
}
//円 & 円 の交点
vector<pt> CCintersect (pair<pt,double> c, pair<pt,double> d) {
    vector<pt> ret;
    double dist = abs(c.first - d.first);
    double cr = c.second;
    double dr = d.second;
     
    if (dist > cr + dr) return ret;
    if (dist < abs(cr - dr)) return ret;
     
    double s = (cr + dr + dist) / 2.;
    double area = sqrt(s * (s - cr) * (s - dr) * (s - dist));
    double h = 2 * area / dist;
     
    pt v = d.first - c.first; v /= abs(v);
    pt m = c.first + sqrt(cr * cr - h * h) * v;
    pt n = v * pt(0, 1);
     
    ret.push_back(m + n * h);
    ret.push_back(m - n * h);
    return ret;
}
//線分a-b とc の距離
double dist_lp(pt a,pt b,pt c){
	if(dot(a-b,c-b) <= 0.0) return abs(c-b);
	if(dot(b-a,c-a) <= 0.0) return abs(c-a);
	return abs(cross(b-a,c-a)) / abs(b-a);
}
//線分が交わる?
bool intersect(pt a,pt b,pt c,pt d){
	return (ccw(a,b,c)*ccw(a,b,d) <= 0 && ccw(c,d,a)*ccw(c,d,b) <= 0);
}
//線分a-b と 線分c-d の距離
double min_dist_ll(pt a,pt b,pt c,pt d){
    if(intersect(a,b,c,d) == true) return 0.0;
    double ret = 1e18;
    ret = min(ret,dist_lp(a,b,c));
    ret = min(ret,dist_lp(a,b,d));
    ret = min(ret,dist_lp(c,d,a));
    ret = min(ret,dist_lp(c,d,b));
    return ret;
}
bool contain_point(vector<pt>ps,pt p){
	double sum = 0;
	//arg no sum wo keisan
	for(int i=0;i<ps.size();i++){
		if(on_segment(mp(ps[i],ps[ (i+1)%ps.size() ]),p)) return 1;
		sum += arg( (ps[ (i+1)%ps.size() ]-p) / (ps[i]-p) );
	}
	return (abs(sum) > 1);
}
bool LCMP(const pt& a,const pt& b){
	if(eq(a.x,b.x)) return a.y < b.y;
	else return a.x < b.x;
}




int n;
pt p[30005];
double deg[30005];
//#define M_PI 3.1415926535897932
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		double a,b;
		scanf("%Lf%Lf",&a,&b);
		p[i] = pt(a,b);
		p[i] *= exp( pt( .0, 1.0*M_PI/180.0 ) );
	}
	for(int i=n;i<=3*n;i++) p[i] = p[i-n];
	for(int i=0;i<3*n;i++){
		pt dif = pt(p[i+1].x-p[i].x,p[i+1].y-p[i].y);
		deg[i] = arg(dif);
		while(deg[i] < 0) deg[i] += 2.0*M_PI;
		while(i && deg[i-1] > deg[i]) deg[i] += 2.0*M_PI;
	}
//	for(int i=0;i<3*n;i++) cout<<deg[i]<<endl;
	double ans = 1e18;
	{
		int c2 = 0,c3 = 0;
		rep(i,n){
			//p[i]-p[(i+1)%n]を通る
			double cur = deg[i];
			double cur2 = cur+120.0*M_PI/180.0;
			double cur3 = cur+240.0*M_PI/180.0;
			while(deg[c2] < cur2) c2++;
			while(deg[c3] < cur3) c3++;
			pt a = p[i], b = p[i+1];
			pt c = p[c2], d = c+(b-a)*exp( pt( .0, 120.0*M_PI/180.0 ) );
			pt e = p[c3], f = e+(b-a)*exp( pt( .0, 240.0*M_PI/180.0 ) );
			pt A = crossPoint(a,b,c,d);
			pt B = crossPoint(c,d,e,f);
			pt C = crossPoint(a,b,e,f);
			ans = min(ans,abs(A-B));
			//cout<<abs(A-B)<<" "<<abs(B-C)<<" "<<abs(C-A)<<endl;
		}
	}
	printf("%.8Lf\n",ans);
}