#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <deque>
#include <time.h>
using namespace std;

const double eps = 1e-8;
const double pi = acos(-1);
const double inf = 1e9;
const int MAXP = 1e3 + 10;

inline int dcmp (double val) { return (fabs(val) < eps) ? 0 : (val > 0 ? 1 : -1); }

// ****************************************************************************************************
// Point
// ****************************************************************************************************
struct Point { double x, y; };

inline void input (Point & a) { scanf("%lf%lf", &a.x, &a.y); }

inline void output (Point & a) { printf("(%.6f,%.6f)", a.x, a.y); }

Point operator + (Point a, Point b) { return { a.x + b.x, a.y + b.y }; }

Point operator - (Point a, Point b) { return { a.x - b.x, a.y - b.y }; }

double operator * (Point a, Point b) { return a.x * b.x + a.y * b.y; }

double operator ^ (Point a, Point b) { return a.x * b.y - a.y * b.x; }

bool operator == (Point a, Point b) { return a.x == b.x && a.y == b.y; }

bool operator < (Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }

inline double norm (Point a) { return sqrt(a.x * a.x + a.y * a.y); }

inline double norm2 (Point a) { return a.x * a.x + a.y * a.y; }

inline double dist (Point a, Point b) { return norm(a - b); }

Point operator * (Point a, double b) { return { a.x * b, a.y * b }; }

Point operator / (Point a, double b) { return { a.x / b, a.y / b }; }

inline Point rotate (Point a, double ang) { return { a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang) }; }

inline Point rotateLeft (Point a) { return { -a.y, a.x }; }

inline Point rotateRight (Point a) { return { a.y, -a.x }; }

inline double angle (Point a) { return atan2(a.y, a.x); }

// while norm(a) != 0
inline Point uni (Point a) { return dcmp(norm(a)) == 0 ? a : (a / norm(a)); }

inline Point operator - (Point a) { return { -a.x, -a.y }; }

// ****************************************************************************************************
// Line 
// ****************************************************************************************************
struct Line { Point s, e; };

inline void input (Line & a) { input(a.s); input(a.e); }

inline void output (Line & a) { output(a.s); output(a.e); }

// a + ang * v
inline Line makeline (Point a, double ang) { return { a, a + (Point){ cos(ang), sin(ang) } }; }

// ax + by + c = 0
inline Line makeline (double a, double b, double c) {
    if (dcmp(a) == 0) return { { 0, - c / b }, { 1, - c / b } };
    if (dcmp(b) == 0) return { { - c / a, 0 }, { - c / a, 1 } };
    return { { 0, - c / b }, { - c / a, 0 } };
}

inline double length (Line a) { return dist(a.s, a.e); }

inline double angle (Point s, Point e) {
	double ret = atan2(e.y - s.y, e.x - s.x);
	if (dcmp(ret) < 0) ret += pi;
	if (dcmp(ret - pi) == 0) ret -= pi;
	return ret;
}

Line operator + (Line a, Point v) { return { a.s + v, a.e + v }; }

// relation between point and segment
// -1 : on the left
// 0 : on
// 1 : on the right
inline int relation (Point p, Point s, Point e) { return dcmp((p - s) ^ (e - s)); }

inline bool pointOnSeg (Point p, Point s, Point e) { return dcmp((p - s) ^ (e - s)) == 0 && dcmp((p - s) * (p - e)) <= 0; }

inline Point pointProjLine (Point p, Point s, Point e) { return s + (e - s) * ((p - s) * (e - s)) / ((e - s) * (e - s)); }

inline double pointDisLine (Point p, Point s, Point e) { return fabs((s - p) ^ (e - p)) / dist(s, e); }

inline double pointDisSeg (Point p, Point s, Point e) {
	return (dcmp((p - s) ^ (e - s)) >= 0 && dcmp((p - e) ^ (s - e)) >= 0) ? pointDisLine(p, s, e) : min(dist(p, s), dist(p, e));
}

inline bool para (Line a, Line b) { return dcmp((a.e - a.s) ^ (b.e - b.s)) == 0; }

// intersection of two segments
// 2 : cross normmally
// 1 : cross unormmally
// 0 : not cross
inline int segCrossSeg (Line a, Line b) {
    if ((dcmp((a.e - a.s) ^ (b.s - a.s)) ^ dcmp((a.e - a.s) ^ (b.e - a.s))) == -2 &&
        (dcmp((b.e - b.s) ^ (a.s - b.s)) ^ dcmp((b.e - b.s) ^ (a.e - b.s))) == -2) return 2;
    return (pointOnSeg(a.s, b.s, b.e) || pointOnSeg(a.e, b.s, b.e) || pointOnSeg(b.s, a.s, a.e) || pointOnSeg(b.e, a.s, a.e));
}

inline bool segCrossSeg_normally (Line a, Line b) {
	return ((dcmp((a.e - a.s) ^ (b.s - a.s)) ^ dcmp((a.e - a.s) ^ (b.e - a.s))) == -2 &&
    		(dcmp((b.e - b.s) ^ (a.s - b.s)) ^ dcmp((b.e - b.s) ^ (a.e - b.s))) == -2);
	/*
	return (relation(a.s, b.s, b.e) ^ relation(a.e, b.s, b.e) == -2 &&
			relation(b.s, a.s, a.e) ^ relation(b.e, a.s, a.e) == -2;
	*/
}

// intersection of segment and line
// 2 : cross normmally
// 1 : cross unormmally
// 0 : not cross
inline int lineCorssSeg (Line a, Line b) {
	int d1 = dcmp((a.e - a.s) ^ (b.s - a.s));
	int d2 = dcmp((a.e - a.s) ^ (b.e - a.s));
	return ((d1 ^ d2) == -2) ? 2 : (d1 == 0 || d2 == 0);
}

// intersection of line and line
// 2 : cross
// 1 : coincide
// 0 : parallel
inline int lineCorssLine (Line a, Line b) {
	return para(a, b) ? (relation(a.s, b.s, b.e) == 0) : 2;
}

// while segCrossSeg(a, b) == 2
inline Point crosspoint (Line a, Line b) {
	double d1 = (a.s - b.s) ^ (b.e - b.s);
	double d2 = (a.e - b.s) ^ (b.e - b.s);
	return (a.e * d1 - a.s * d2) / (d1 - d2);
}

inline Point symmetrypoint (Point p, Line a) {
	return pointProjLine(p, a.s, a.e) * 2 - p;
}

inline double segDisSeg (Line a, Line b) {
	return min(min(pointDisSeg(a.s, b.s, b.e), pointDisSeg(a.e, b.s, b.e)), 
		   	min(pointDisSeg(b.s, a.s, a.e), pointDisSeg(b.e, a.s, a.e)));
}

// ****************************************************************************************************
// Circle
// ****************************************************************************************************

struct Circle { Point o; double r; };

inline void input (Circle & c) { input(c.o); scanf("%lf", &c.r); }

inline void output (Circle & c) { printf("%.6f %.6f %.6f\n", c.o.x, c.o.y, c.r); }

inline Circle excircle (Point a, Point b, Point c) {
	Line u = { (a + b) / 2, (a + b) / 2 + rotateLeft(b - a) };
	Line v = { (b + c) / 2, (b + c) / 2 + rotateLeft(c - b) };
	Point p = crosspoint(u, v);
	return { p, dist(p, a) }; 
}

inline Circle incircle (Point a, Point b, Point c) {
	Line u = makeline(a, (angle(b - a) + angle(c - a)) / 2);
	Line v = makeline(b, (angle(a - b) + angle(c - b)) / 2);
	Point p = crosspoint(u, v);
	return { p, pointDisLine(p, a, b) }; 
}

bool operator == (Circle a, Circle b) { return a.o == b.o && dcmp(a.r - b.r); }

bool operator < (Circle a, Circle b) { return a.o == b.o ? dcmp(a.r - b.r) : a.o < b.o; }

inline double Area (Circle c) { return pi * c.r * c.r; }

inline double Circumference (Circle c) { return 2 * pi * c.r; }

// relation of point / segment / line and circle
// 1 : ex
// 0 : on
// -1 : in
inline int relation (Point p, Circle c) { return dcmp(dist(p, c.o) - c.r); }

inline int relationSeg (Line l, Circle c) { return dcmp(pointDisSeg(c.o, l.s, l.e) - c.r); }

inline int relationLine (Line l, Circle c) { return dcmp(pointDisLine(c.o, l.s, l.e) - c.r); }

// relation of two circles
// 2 : ex not cross
// 1 : ex tangent
// 0 : cross
// -1 : in tangent
// -2 : in not cross
inline int relation (Circle a, Circle b) {
	double d = dist(a.o, b.o);
	int d1 = dcmp(d - a.r - b.r), d2 = dcmp(d - fabs(a.r - b.r));
	return (d1 >= 0) ? (d1 + 1) : (d2 - 1);
}

inline int crosspointCircle (Circle a, Circle b, Point & p1, Point & p2) {
	int rel = relation(a, b);
	if (abs(rel) == 2) return 0;
	double d = dist(a.o, b.o);
	double l = (d * d + a.r * a.r - b.r * b.r) / (2 * d);
	double h = sqrt(a.r * a.r - l * l);
	p1 = a.o + uni(b.o - a.o) * l + uni(rotateLeft(b.o - a.o)) * h;
	p2 = p1 + uni(rotateRight(b.o - a.o)) * (2 * h);
	return 2 - abs(rel);
}

inline int crosspointLine (Line a, Circle c, Point & p1, Point &p2) {
	int rel = relationLine(a, c);
	if (rel == 1) return 0;
	double d = pointDisLine(c.o, a.s, a.e);
	d = sqrt(c.r * c.r - d * d);
	p1 = pointProjLine(c.o, a.s, a.e) + uni(a.e - a.s) * d;
	p2 = p1 - uni(a.e - a.s) * (2 * d);
	return 1 - rel;
}

// circles with radius r ans passing point a and point b
inline int circlePassTwoPoint (Point p1, Point p2, double rr, Circle & a, Circle & b) {
	a = { p1, rr }; b = { p2, rr };
 	return crosspointCircle(a, b, a.o, b.o);
}

// circles with radius r tangent by line l and passing point p
inline int circlePassLineAndPoint (Line l, Point p, double rr, Circle & a, Circle & b) {
	double d = pointDisLine(p, l.s, l.e);
	if (dcmp(d - 2 * rr) > 0) return 0;
	if (dcmp(d) == 0) {
		a = { p + uni(rotateLeft(l.e - l.s)) * rr, rr };
		b = { p + uni(rotateRight(l.e - l.s)) * rr, rr };
		return 2;
	};
	a.r = b.r = rr;
	return crosspointLine(l + rotateRight(uni(l.e - l.s)) * (rr * relation(p, l.s, l.e)), { p, rr }, a.o, b.o);
}

// circles with radius r tangent by two line
inline int circlePassTwoLine (Line u, Line v, double rr, Circle & c1, Circle & c2, Circle & c3, Circle & c4) {
	if (para(u, v)) return 0;
	Point a = rotateRight(uni(u.e - u.s)) * rr;
	Point b = rotateRight(uni(v.e - v.s)) * rr;
	c1 = { crosspoint(u + a, v + b), rr };
	c2 = { crosspoint(u + a, v + (-b)), rr };
	c3 = { crosspoint(u + (-a), v + b), rr };
	c4 = { crosspoint(u + (-a), v + (-b)), rr };
	return 4;
}

// circles with radius r tangent by two circle
inline int circlePassTwoCircle (Circle cx, Circle cy, double rr, Circle & a, Circle & b) {
	a.r = b.r = rr;
	return crosspointCircle({ cx.o, cx.r + rr }, { cy.o, cy.r + rr }, a.o, b.o);
}

// lines tangent by circle pass one point
inline int tangentLine (Point p, Circle c, Line & u, Line & v) {
	int rel = relation(p, c);
	if (rel == -1) return 1 + rel;
	double l = c.r * c.r / dist(c.o, p);
	double h = sqrt(c.r * c.r - l * l);
	u = { p, c.o + uni(p - c.o) * l + rotateLeft(uni(p - c.o)) * h };
	v = { p, c.o + uni(p - c.o) * l - rotateLeft(uni(p - c.o)) * h };
	return 1 + rel;
}

inline double areaCircle (Circle a, Circle b) {
	int rel = relation(a, b);
	if (rel <= 0) return min(Area(a), Area(b));
	if (rel == 2) return 0;
	double d = dist(a.o, b.o);
	double p = (d + a.r + b.r) / 2;
	double s = 2 * sqrt(p * (p - d) * (p - a.r) * (p - b.r));
	double s1 = acos((a.r * a.r + d * d - b.r * b.r) / (2 * a.r * d)) * a.r * a.r;
	double s2 = acos((b.r * b.r + d * d - a.r * a.r) / (2 * b.r * d)) * b.r * b.r;
	return s1 + s2 - s;
}

// area by oab and circle
inline double areaTriangle (Point a, Point b, Circle c) {
	if (dcmp((c.o - a) ^ (c.o - b)) == 0) return 0;
	Point p[4]; int n = 0;
	p[n ++] = a;
	if (crosspointLine({ a, b }, c, p[1], p[2]) == 2) {
		if (dcmp((a - p[1]) * (b - p[1])) < 0) p[n ++] = p[1];
		if (dcmp((a - p[2]) * (b - p[2])) < 0) p[n ++] = p[2];
	}
	p[n ++] = b;
	if (n == 4 && dcmp((p[0] - p[1]) * (p[2] - p[1])) > 0) swap(p[1], p[2]);
	
	double ret = 0;
	for (int i = 1; i < n; i++) {
		if (relation(p[i - 1], c) == 1 || relation(p[i], c) == 1) {
			ret += c.r * c.r * acos((norm2(p[i - 1] - c.o) + norm2(p[i] - c.o) - norm2(p[i - 1] - p[i])) /
				 (2 * dist(p[i - 1], c.o) * dist(p[i], c.o))) / 2;
		} else {
			ret += fabs((p[i - 1] - c.o) ^ (p[i] - c.o)) / 2;
		}
	}
	return ret;
}

inline Circle circleMinCover (Point * p, int n) {
	srand(time(NULL));
	random_shuffle(p, p + n);

	Circle c = { p[0], 0 };
	for (int i = 1; i < n; i++) {
		if (relation(p[i], c) <= 0) continue;
		c = { p[i], 0 };
		for (int j = 0; j < i; j++) {
			if (relation(p[j], c) <= 0) continue;
			c = { (p[i] + p[j]) / 2, dist(p[i], p[j]) / 2 };
			for (int k = 0; k < j; k++) {
				if (relation(p[k], c) <= 0) continue;
				c = excircle(p[i], p[j], p[k]);
			}
		}
	}
	return c;
}

// ****************************************************************************************************
// Polygon
// ****************************************************************************************************

struct Polygon { 
	Point p[MAXP];
	int n;

	Polygon (int n): n(n) {}

	Polygon () {}

	inline void Convex (Polygon & ret) {
		sort(p, p + n);

		int m = 0;
		for (int i = 0; i < n; i++) {
			while (m > 1 && dcmp((ret.p[m - 1] - ret.p[m - 2]) ^ (p[i] - ret.p[m - 2])) <= 0)
				m --;
			ret.p[m ++] = p[i];
		}
		int k = m;
		for (int i = n - 2; i >= 0; i--) {
			while (m > k && dcmp((ret.p[m - 1] - ret.p[m - 2]) ^ (p[i] - ret.p[m - 2])) <= 0)
				m --;
			ret.p[m ++] = p[i];
		}
		ret.n = m - (m > 1);
	}

	inline void ConvexStable (Polygon & ret) {
		sort(p, p + n);

		int m = 0;
		for (int i = 0; i < n; i++) {
			while (m > 1 && dcmp((ret.p[m - 1] - ret.p[m - 2]) ^ (p[i] - ret.p[m - 2])) < 0)
				m --;
			ret.p[m ++] = p[i];
		}
		int k = m;
		for (int i = n - 2; i >= 0; i--) {
			while (m > k && dcmp((ret.p[m - 1] - ret.p[m - 2]) ^ (p[i] - ret.p[m - 2])) < 0)
				m --;
			ret.p[m ++] = p[i];
		}
		ret.n = m - (m > 1);
	}

	inline bool isConvex (void) {
		bool s[3] = { false, false, false };
		for (int i = 0, j = (i + 1) % n, k; i < n; i++, j = k) {
			k = (i + 2) % n;
			s[dcmp((p[j] - p[i]) ^ (p[k] - p[i])) + 1] = true;
			// if (s[1]) return false; // if strictly
			if (s[0] && s[2]) return false;
		}
		return true;
	}

	// relation with point
	// 1 : ex
	// 0 : on endpoint or line
	// -1 : in
	inline int relation (Point q) {
		int cnt = 0, k, d1, d2;
		for (int i = 0, j; i < n; i++) {;
			j = (i + 1) % n;
			if (pointOnSeg(q, p[i], p[j])) return 0;
			k = dcmp((q - p[i]) ^ (p[j] - p[i]));
			d1 = dcmp(p[i].y - q.y);
			d2 = dcmp(p[j].y - q.y);
			if (k > 0 && d1 < 0 && d2 >= 0) cnt ++;
			if (k < 0 && d2 < 0 && d1 >= 0) cnt --;
		}
		return 1 - 2 * (cnt != 0);
	}

	inline int relationConvex (Point q) {
		Point g = (p[0] + p[n / 3] + p[2 * n / 3]) / 3;
		int st = 0, en = n;
		while (st + 1 < en) {
			int md = (st + en) >> 1;
			if (dcmp((p[st] - g) ^ (p[md] - g)) > 0) {
				if (dcmp((p[st] - g) ^ (q - g)) >= 0 && dcmp((p[md] - g) ^ (q - g)) < 0) en = md;
				else st = md;
			} else {
				if (dcmp((p[st] - g) ^ (q - g)) < 0 && dcmp((p[md] - g) ^ (q - g)) >= 0) st = md;
				else en = md;
			}
		}
		en %= n;
		return dcmp((p[en] - q) ^ (p[st] - q));
	} 

	inline double Circumference (void) {
		double ret = 0;
		for (int i = 0; i < n; i++) ret += dist(p[i], p[(i + 1) % n]);
		return ret / 2;
	}

	inline double Area (void) {
		if (n < 3) return 0;
		double ret = 0;
		for (int i = 0; i < n; i++) ret += p[i] ^ p[(i + 1) % n];
		return fabs(ret / 2);
	}

	// direction of points
	// 1 : counter-clockwise
	// 2 : clockwise
	inline double Direction (void) {
		return dcmp(Area()) > 0;
	}

	inline Point Masscenter (void) {
		Point ret = { 0, 0 };
		for (int i = 0, j; i < n; i++) {
			j = (i + 1) % n;
			ret = ret + (p[i] + p[j]) * (p[j] ^ p[i]);
		}
		double area = Area();
		return dcmp(area) ? (ret / (area * 6)) : ret;
	}
};

inline void input (Polygon & s) {
	scanf("%d", &s.n);
	for (int i = 0; i < s.n; i++) {
		input(s.p[i]);
	}
}

inline void output (Polygon & s) {
	printf("%d\n", s.n);
	for (int i = 0; i < s.n; i++) {
		output(s.p[i]); puts("");
	}
	puts("");
}

inline double PolygonAreaCircle (Polygon & poly, Circle & c) {
	double ret = 0;
	for (int i = 0, j; i < poly.n; i++) {
		j = (i + 1) % poly.n;
		ret += relation(c.o, poly.p[i], poly.p[j]) *
			areaTriangle(poly.p[i], poly.p[j], c);
	}
	return fabs(ret);
}

inline int Convex (Point * p, int n, Point * ret) {
	sort(p, p + n);

	int m = 0;
	for (int i = 0; i < n; i++) {
		for (; m > 1 && dcmp((ret[m - 1] - ret[m - 2]) ^ (p[i] - ret[m - 2])) <= 0; m --);
		ret[m ++] = p[i];
	}
	int k = m;
	for (int i = n - 2; i >= 0; i--) {
		for (; m > k && dcmp((ret[m - 1] - ret[m - 2]) ^ (p[i] - ret[m - 2])) <= 0; m --);
		ret[m ++] = p[i];
	}
	return m - (m > 1);
}

Point _p;
inline bool cmp (Point a, Point b) {
	a = a - _p; b = b - _p; return dcmp(a ^ b) == 0 ? (norm2(a) < norm2(b)) : (dcmp(a ^ b) > 0);
}

inline int graham (Point * p, int n, Point * ret) {
	for (int i = 1; i < n; i++) if (p[i] < p[0]) swap(p[i], p[0]); _p = p[0];
	sort(p + 1, p + n, cmp);

	int m = 0; ret[m ++] = p[0]; ret[m ++] = p[1];
	for (int i = 2; i < n; i++) {
		for (; m > 1 && dcmp((ret[m - 1] - ret[m - 2]) ^ (p[i] - ret[m - 2])) <= 0; m --);
		ret[m ++] = p[i];
	}
	return m;
}

double DisDiameter (Point * p, int n) {
	double ret = 0;
	p[n] = p[0];
	for (int i = 0, j = 1; i < n; i++) {
		for (; dcmp((p[j + 1] - p[j]) ^ (p[i + 1] - p[i])) < 0; j = (j + 1) % n);
		ret = max(ret, (p[j] - p[i]) * (p[j] - p[i]));
	}
	return ret; 
}

double DisWidth (Point * p, int n) {
	double ret = 1e15;
	p[n] = p[0];
	for (int i = 0, j = 1; i < n; i++) {
		for (; dcmp((p[j + 1] - p[j]) ^ (p[i + 1] - p[i])) < 0; j = (j + 1) % n);
		ret = min(ret, pointDisLine(p[j], p[i], p[(i + 1) % n]));
	}
	return ret;
}

// strict convex
double LeastRect (Point * p, int n) {
	if (n < 3) return 0;
	int d, u, l, r;
	p[n] = p[0];
	for (r = 1; dcmp((p[r + 1] - p[r]) * (p[1] - p[0])) > 0; r = (r + 1) % n);
	for (l = r; dcmp((p[l + 1] - p[l]) * (p[0] - p[1])) >= 0; l = (l + 1) % n);
	double ret = 1e30;
	for (d = 0, u = 1; d < n; d++) {
		for (; dcmp((p[u + 1] - p[u]) ^ (p[d + 1] - p[d])) < 0; u = (u + 1) % n);
		for (; dcmp((p[r + 1] - p[r]) * (p[d + 1] - p[d])) > 0; r = (r + 1) % n);
		for (; dcmp((p[l + 1] - p[l]) * (p[d] - p[d + 1])) > 0; l = (l + 1) % n);
		ret = min(ret, ((p[d + 1] -  p[d]) ^ (p[u] - p[d])) *
			((p[r] - p[l]) * (p[d + 1] - p[d])) / 
			((p[d + 1] - p[d]) * (p[d + 1] - p[d])) ); // area
		// ret = min(ret, 2 * (w + h)); // circumference
	}
	return ret;
}



// ****************************************************************************************************
// Circles
// ****************************************************************************************************

inline bool in (Circle a, Circle b) {
	return relation(a, b) < 0 && (dcmp(a.r - b.r) <= 0);
}

struct Circles {
	Circle c[MAXP];
	int n;

	Circles (int n): n(n) {}

	Circles () {}

	double s[MAXP]; // area covered k times;

	void initOR (void) {
		bool ok[MAXP]; 
		memset(ok, 1, sizeof(ok));
		for (int i = 0, j; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (i == j || !ok[j]) continue;
				if (c[i] == c[j] || in(c[i], c[j])) break;
			}
			if (j < n) ok[i] = 0;
		}
		int m = 0;
		for (int i = 0; i < n; i++) {
			if (!ok[i]) c[m ++] = c[i];
		}
		n = m;
	}

	// double areaCircles (void) {
		
	// }
};

// ****************************************************************************************************
// HalfPlanes
// ****************************************************************************************************

inline bool cmpHP (const Line & u, const Line & v) {
	int ret = dcmp(angle(u.e - u.s) - angle(v.e - v.s));
	return ret == 0 ? relation(u.s, v.s, v.e) <= 0 : ret < 0;
}

inline int HalfPlanes (Line * lines, int n, Point * p) {
	sort(lines, lines + n, cmpHP);
	deque<Line> deq;
	deque<Point> ret;
	deq.push_back(lines[0]);
	for (int i = 1; i < n; i++) {
		if (dcmp(angle(lines[i].e - lines[i].s) - angle(lines[i - 1].e - lines[i - 1].s)) == 0) 
			continue;
		for (; ret.size() && relation(ret.back(), lines[i].s, lines[i].e) > 0; ret.pop_back(), deq.pop_back());
		for (; ret.size() && relation(ret.front(), lines[i].s, lines[i].e) > 0; ret.pop_front(), deq.pop_front());
		ret.push_back(crosspoint(deq.back(), lines[i]));
		deq.push_back(lines[i]);
	}
	for (; ret.size() && relation(ret.back(), deq.front().s, deq.front().e) > 0; ret.pop_back(), deq.pop_back());
	for (; ret.size() && relation(ret.front(), deq.back().s, deq.back().e) > 0; ret.pop_front(), deq.pop_front());
	ret.push_back(crosspoint(deq.front(), deq.back()));

	int m = 0;
	while (ret.size()) {
		p[m ++] = ret.front();
		ret.pop_front();
	}
	return m;
}


inline void HalfPlaneCut (Polygon & s, Line line, Polygon & ret) {
	int & m = ret.n; m = 0;
	for (int i = 0, j; i < s.n; i++) {
		if (relation(s.p[i], line.s, line.e) <= 0) {
			ret.p[m ++] = s.p[i];
		} else {
			j = (s.n - 1 + i) % s.n;
			if (relation(s.p[j], line.s, line.e) < 0)
				ret.p[m ++] = crosspoint({ s.p[i], s.p[j] }, line);
			j = (1 + i) % s.n;
			if (relation(s.p[j], line.s, line.e) < 0)
				ret.p[m ++] = crosspoint({ s.p[i], s.p[j] }, line);
		}
	}
}

const int N = 100;

Point p[N];

int main (void) {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lf%lf", &p[i].x, &p[i].y);
	Circle c = circleMinCover(p + 1, n);
	printf("%.8f\n", c.r);
}

Measured memory_bytes: 256