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 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 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]);
}

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 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]);
}

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;
}