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:
/*  -*- coding: utf-8 -*-
 *
 * 3056.cc: Equilateral Triangle
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 10000;
const double PI = acos(-1.0);
const double TH60 = PI * 2 * 60 / 360;
const double C60 = cos(TH60), S60 = sin(TH60);
const double DINF = 1e60;

/* typedef */

template <typename T>
struct Pt {
  T x, y;

  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &pt) : x(pt.x), y(pt.y) {}

  Pt<T> operator+(const Pt<T> pt) const { return Pt<T>(x + pt.x, y + pt.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> pt) const { return Pt<T>(x - pt.x, y - pt.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }
  T d2() { return x * x + y * y; }
  double d() { return sqrt(d2()); }

  Pt<T> rot60() { return Pt<T>(C60 * x - S60 * y, S60 * x + C60 * y); }
  Pt<T> rot300() { return Pt<T>(C60 * x + S60 * y, -S60 * x + C60 * y); }

  Pt<T> normalize() {
    double d0 = d();
    return (d0 != 0.0) ? Pt<T>(x / d0, y / d0) : *this;
  }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  bool read() { return (scanf("%lf%lf", &x, &y) == 2); }
  void print() { printf("(%lf,%lf)", x, y); }
};

typedef Pt<double> pt;

struct CL {
  pt p;
  double t0, t1;
  CL() {}
  CL(const pt& _p, double _t0, double _t1) : p(_p), t0(_t0), t1(_t1) {}
};

/* global variables */

pt ps[MAX_N];

/* subroutines */

bool cross_lines(const pt& ap, const pt av, const pt& bp, const pt bv,
		 CL& cl) {
  double op01 = av.cross(bv);
  //if (op01 == 0.0) return false; /* need to handle parallel?? */

  if (op01 == 0.0) {
    pt v = bp - ap;
    if (v.cross(av) != 0.0) return false;

    pt a1 = ap + av;
    pt b1 = bp + bv;

    return
      ((bp - ap).dot(b1 - ap) <= 0.0 ||
       (bp - a1).dot(b1 - a1) <= 0.0 ||
       (ap - bp).dot(a1 - bp) <= 0.0 ||
       (ap - b1).dot(a1 - b1) <= 0.0);
  }

  pt v = bp - ap;
  double op0 = v.cross(av);
  double op1 = v.cross(bv);

  double t0 = op1 / op01;
  double t1 = op0 / op01;

  cl.p = bv * t1 + bp;
  cl.t0 = t0;
  cl.t1 = t1;

  return true;
  //return (0.0 <= cl.t0 && cl.t0 <= 1.0 && 0.0 <= cl.t1 && cl.t1 <= 1.0);
}

/* main */

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) ps[i].read();

  double minl = DINF;
  for (int i = 0; i < n; i++) {
    pt &p0 = ps[i], &p1 = ps[(i + 1) % n];
    pt v0 = (p1 - p0).normalize();
    pt v1 = v0.rot60(), v2 = v0.rot300();
    double mint = 0.0, maxt = 0.0;

    for (int j = 0; j < n; j++) {
      CL cl1, cl2;
      cross_lines(p0, v0, ps[j], v1, cl1);
      cross_lines(p0, v0, ps[j], v2, cl2);
      if (mint > cl1.t0) mint = cl1.t0;
      if (maxt < cl2.t0) maxt = cl2.t0;
    }
    double l = maxt - mint;
    if (minl > l) minl = l;
  }

  printf("%.8lf\n", minl);
  return 0;
}