Problem: Fair Chocolate-Cutting

You are given a flat piece of chocolate of convex polygon shape. You are to cut it into two pieces of precisely the same amount with a straight knife.

Write a program that computes, for a given convex polygon, the maximum and minimum lengths of the line segments that divide the polygon into two equal areas.

The figures below correspond to first two sample inputs. Two dashed lines in each of them correspond to the equal-area cuts of minimum and maximum lengths.

<image>
Figure F.1. Sample Chocolate Pieces and Cut Lines

Input

The input consists of a single test case of the following format.


$n$
$x_1$ $y_1$
...
$x_n$ $y_n$


The first line has an integer $n$, which is the number of vertices of the given polygon. Here, $n$ is between 3 and 5000, inclusive. Each of the following $n$ lines has two integers $x_i$ and $y_i$, which give the coordinates ($x_i, y_i$) of the $i$-th vertex of the polygon, in counterclockwise order. Both $x_i$ and $y_i$ are between 0 and 100 000, inclusive.

The polygon is guaranteed to be simple and convex. In other words, no two edges of the polygon intersect each other and interior angles at all of its vertices are less than $180^\circ$.

Output

Two lines should be output. The first line should have the minimum length of a straight line segment that partitions the polygon into two parts of the equal area. The second line should have the maximum length of such a line segment. The answer will be considered as correct if the values output have an absolute or relative error less than $10^{-6}$.

Sample Input 1


4
0 0
10 0
10 10
0 10


Sample Output 1


10
14.142135623730950488


Sample Input 2


3
0 0
6 0
3 10


Sample Output 2


4.2426406871192851464
10.0


Sample Input 3


5
0 0
99999 20000
100000 70000
33344 63344
1 50000


Sample Output 3


54475.580091580027976
120182.57592539864775


Sample Input 4


6
100 350
101 349
6400 3440
6400 3441
1200 7250
1199 7249


Sample Output 4


4559.2050019027964982
6216.7174287968524227






Example

Input

4
0 0
10 0
10 10
0 10


Output

10
14.142135623730950488

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(W,n)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {REP(aaa,i){REP(bbb,j)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
//--------geometry original ------------------
#define curr(PP, i) PP[i]
#define next(PP, i) PP[(i+1)%PP.size()]
#define diff(PP, i) (next(PP, i) - curr(PP, i))
#define X real()
#define Y imag()

typedef long long ll;
typedef pair<ll, ll> P;

const double EPS = 1e-7;
const double PI = acos(-1.0);
typedef complex<double> point;
namespace std {
	bool operator < (const point& a, const point& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}

	bool operator == (const point& a,const point& b) {
		return (abs(a.real() - b.real()) < EPS && abs(a.imag() - b.imag()) < EPS);
	}
}
struct circle {
	point p; double r;
	circle(){}
	circle(const point &p, double r) : p(p), r(r) { }
};
struct segment : public vector<point> {
	segment(const point &a, const point &b) {
		push_back(a); push_back(b);
	}
};

double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}

double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}

/*
a → b で時計方向に折れて b → c
a → b で半時計方向に折れて b → c
a → b で逆を向いて a を通り越して b → c
a → b でそのまま b → c
a → b で逆を向いて b → c ( または b == c )
*/

int ccw(point a, point b, point c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

bool intersectLL(const segment &l, const segment &m) {
	return abs(cross(l[1] - l[0], m[1] - m[0])) > EPS || // non-parallel
		abs(cross(l[1] - l[0], m[0] - l[0])) < EPS;   // same line
}
bool intersectLS(const segment &l, const segment &s) {
	return cross(l[1] - l[0], s[0] - l[0])*       // s[0] is left of l
		cross(l[1] - l[0], s[1] - l[0]) < EPS; // s[1] is right of l
}
bool intersectLP(const segment &l, const point &p) {
	return abs(cross(l[1] - p, l[0] - p)) < EPS;
}
bool intersectSP(const segment &s, const point &p) {
	return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; // triangle inequality
}
//端点の交差も考える
bool intersectSS(const segment &s, const segment &t) {
	return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
		ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}

point projection(const segment &l, const point &p) {
	double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
	return l[0] + t*(l[0] - l[1]);
}
point reflection(const segment &l, const point &p) {
	return p + 2. * (projection(l, p) - p);
}
double distanceLP(const segment &l, const point &p) {
	return abs(p - projection(l, p));
}
double distanceLL(const segment &l, const segment &m) {
	return intersectLL(l, m) ? 0 : distanceLP(l, m[0]);
}
double distanceLS(const segment &l, const segment &s) {
	if (intersectLS(l, s)) return 0;
	return min(distanceLP(l, s[0]), distanceLP(l, s[1]));
}
double distanceSP(const segment &s, const point &p) {
	const point r = projection(s, p);
	if (intersectSP(s, r)) return abs(r - p);
	return min(abs(s[0] - p), abs(s[1] - p));
}
double distanceSS(const segment &s, const segment &t) {
	if (intersectSS(s, t)) return 0;
	return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
		min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
double distancePP(const point &a,const point &b){
	return abs(a-b);
}

//交点
point crosspoint(const segment &l, const segment &m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
	if (abs(A) < EPS) return point(INF,INF); // !!!PRECONDITION NOT SATISFIED!!!
	return m[0] + B / A * (m[1] - m[0]);
}

//凸包
vector<point> convex_hull(vector<point> ps) {
	int n = ps.size(), k = 0;
	sort(ps.begin(), ps.end());
	vector<point> ch(2*n);
	for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
		while (k >= 2 && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
	for (int i = n-2, t = k+1;i >= 0; ch[k++] = ps[i--]) // upper-hull
		while (k >= t && ccw(ch[k-2], ch[k-1], ps[i]) == -1) --k;
	ch.resize(k - 1);
	return ch;
}

/*多角形内包判定
OUT:0
ON:1
IN:2
*/

int contains(const vector<point>& Poly, const point& p) {
	bool in = false;
	for (int i = 0; i < Poly.size(); ++i) {
		point a = curr(Poly, i) - p, b = next(Poly, i) - p;
		if (imag(a) > imag(b)) swap(a, b);
		if (imag(a) <= 0 && 0 < imag(b))
			if (cross(a, b) < 0) in = !in;
		if (cross(a, b) == 0 && dot(a, b) <= 0) return 1;
	}
	return in ? 2 : 0;
}

//見えるか(可視グラフ用)
bool block_off(const point &a, const point &b, const vector<point> &obj) {
  point m = (a+b)/2.0;
  bool on = false, in = false;
  for (int j = 0; j < obj.size(); ++j) {
    point c = curr(obj,j), d = next(obj,j);
    if (imag(d) < imag(c)) swap(c, d);
    if (cross(a-c,b-c) * cross(a-d,b-d) < 0 &&    // strictly intersect.
        cross(c-a,d-a) * cross(c-b,d-b) < 0) return true;
    if (cross(a-c,b-c) == 0 && dot(a-c,b-c) < 0) return true;
    if (imag(c) <= imag(m) && imag(m) < imag(d))  // strictly contain.
      if (cross(c-m,d-m) < 0) in = !in;
    if (cross(c-m,d-m) == 0 && dot(c-m,d-m) <= 0) on = true;
  }
  return !on && in;
}

//面積
double area(const vector<point>& p) {
	double A = 0;
	for (int i = 0; i < p.size(); ++i)
		A += cross(curr(p, i), next(p, i));
	return A / 2.;
}

//角度足し算
double add_rad(double a,double b){
	double ret = a + b;
	if(ret > PI)ret -= 2 * PI;
	return ret;
}

//なす角(vector)
double angle(const point &a,const point &b) {
	auto tmp = abs(arg(a) - arg(b));
	return min(tmp, 2 * PI - tmp);
}

double angle(const segment &s1,const segment &s2) {
	return angle(s1[1] - s1[0], s2[1] - s2[0]);
}

//点の回転
point rotate(const point &p, double rad) {
	double x = p.real() * cos(rad) - p.imag() * sin(rad);
	double y = p.imag() * cos(rad) + p.real() * sin(rad);
	return point(x, y);
}

//並行
bool isParallel(const point &a, const point &b){
    return abs(cross(a,b)) < EPS;
}
bool isParallel(const segment &a, const segment &b){
    return isParallel(a[1]-a[0], b[1]-b[0]);
}
//直行
bool isOrthogonal(const point &a,const point &b){
	return abs(angle(a,b) - PI / 2) < EPS;
}
bool isOrthogonal(const segment &a,const segment &b){
	return isOrthogonal(a[1]-a[0],b[1]-b[0]);
}
//凸包判定
bool isConvex(vector<point> poly){
	int sz = poly.size();
	REP(i,sz){
		int tmp = ccw(poly[i],poly[(i+1)%sz],poly[(i+2)%sz]);
		if(tmp == -1){
			return false;
		}
	}
	return true;
}

double convex_diameter(const vector<point> &pt) {
  const int n = pt.size();
  int is = 0, js = 0;
  for (int i = 1; i < n; ++i) {
    if (imag(pt[i]) > imag(pt[is])) is = i;
    if (imag(pt[i]) < imag(pt[js])) js = i;
  }
  double maxd = norm(pt[is]-pt[js]);

  int i, maxi, j, maxj;
  i = maxi = is;
  j = maxj = js;
  do {
    if (cross(diff(pt,i), diff(pt,j)) >= 0) j = (j+1) % n;
    else i = (i+1) % n;
    if (norm(pt[i]-pt[j]) > maxd) {
      maxd = norm(pt[i]-pt[j]);
      maxi = i; maxj = j;
    }
  } while (i != is || j != js);
  return sqrt(maxd); /* farthest pair is (maxi, maxj). */
}

vector<point> convex_cut(const vector<point> P, const segment& l) {
  vector<point> Q;
  for (int i = 0; i < P.size(); ++i) {
    point A = curr(P, i), B = next(P, i);
    if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
    if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
      Q.push_back(crosspoint(segment(A, B), l));
  }
  return Q;
}

int n;
vector<point> v;
double mi = INF;
double ma = 0;
double sumS,nowS;

double triArea(int a,int b,int c){
	a %= n;b %= n;c %= n;
	if(a == b || b == c || c == a)return 0;
	vector<point> tmp = {v[a],v[b],v[c]};
	return area(tmp);
}

void checkVertex(int p,int q) {
	p %= n;q %= n;
	double remain = (sumS / 2) - nowS;
	double rate = remain / triArea(p,q,q+1);
	point tmp = v[q] + rate * (v[(q+1)%n] - v[q]);
	mi = min(mi, distancePP(v[p],tmp));
	ma = max(ma, distancePP(v[p],tmp));
}

double seica(int a,int b){
	a %= n;b %= n;
	vector<point> tmp;
	int i = a;
	while(1){
		tmp.EB(v[i]);
		if(i == b)break;
		i = (i + 1) % n;
	}
	if(tmp.size() < 3)return 0;
	else return area(tmp);
}

void checkSegment(int p,int q){
	p %= n;q %= n;
	nowS -= triArea(p,p+1,q);
	segment a(v[(p+1)%n],v[p]);
	segment b(v[q],v[(q+1)%n]);
	point crossP = crosspoint(a,b);
	if(crossP == point(INF,INF)){
		double sqS = area({v[p],v[(p+1)%n],v[q],v[(q+1)%n]});
		if(nowS + sqS < sumS / 2 + EPS)return;
		bool flag = false;
		if(intersectSP(b,projection(b,a[0])) || intersectSP(b,projection(b,a[1])))flag = true;
		if(intersectSP(a,projection(a,b[0])) || intersectSP(a,projection(a,b[1])))flag = true;
		if(!flag)return;
		mi = min(mi,distanceLP(b,a[0]));
		return;
	}
	double tmpS;
	if(distancePP(crossP,a[0]) > distancePP(crossP,a[1]) + EPS){
		tmpS = seica(q+1,p);
		swap(a[0],a[1]);
		swap(b[0],b[1]);
	}
	else{
		tmpS = seica(p+1,q);
	}
	double theta = angle(a, b);
	double T = distancePP(crossP,a[0]) * distancePP(crossP, b[0]) * sin(theta) / 2;
	double leg = (2 * (T - tmpS) + sumS) / sin(theta);
	bool flag = false;
	if(leg > distancePP(a[1],crossP) * distancePP(a[1],crossP) + EPS)flag = true;
	if(leg + EPS < distancePP(a[0],crossP) * distancePP(a[0],crossP))flag = true;
	if(leg > distancePP(b[1],crossP) * distancePP(b[1],crossP) + EPS)flag = true;
	if(leg + EPS <  distancePP(b[0],crossP) * distancePP(b[0],crossP))flag = true;
	if(flag)return;
	mi = min(mi,2 * sqrt(leg) * sin(theta / 2));
}

int main() {

	cin >> n;
	REP(i,n){
		double a,b;cin >> a >> b;
		v.EB(a,b);
	}

	int q = 1;
	sumS = area(v);
	REP(i,n){
		while(nowS + triArea(i,q,q+1) < sumS / 2 + EPS){
			nowS += triArea(i,q,q+1);
			q++;
		}
		checkVertex(i, q);
		checkSegment(i, q);
	}

	cout << Decimal << mi << endl;
	cout << Decimal << ma << endl;

	return 0;
}