//
//
// http://cs.smith.edu/classwiki/images/c/c8/Mitchell.MinPerim.pdf
// https://www.ics.uci.edu/~eppstein/pubs/EppOveRot-DCG-92.pdf
// https://en.wikipedia.org/wiki/Well-separated_pair_decomposition
// http://www.algorithmic-solutions.info/leda_manual/geo_alg.html
//
// future work:
//   boolean operations (polygonal region overlay; 人間には実装無理では)
//   ham sandwitch cut https://www.ti.inf.ethz.ch/ew/lehre/CG09/materials/v11.pdf

#include <list>
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <iomanip>
#include <queue>
#include <set>
#include <functional>
#include <ctime>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <list>

using namespace std;

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(x,a) { auto y=(x); if (sign(y-a)) { cout << "line " << __LINE__  << #x << " = " << y << " != " << a << endl; exit(-1); } }
double urand() { return rand() / (1.0 + RAND_MAX); }

// === tick a time ===
#include <ctime>
double tick() {
    static clock_t oldtick;
    clock_t newtick = clock();
    double diff = 1.0*(newtick - oldtick) / CLOCKS_PER_SEC;
    oldtick = newtick;
    return diff;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    for (int i = 0; i < v.size(); os << v[i++])
        if (i > 0) os << " ";
    os << "]";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v) {
    os << "[";
    for (int i = 0; i < v.size(); os << v[i++])
        if (i > 0) os << endl << " ";
    os << "]";
    return os;
}

const double PI = acos(-1.0);

// implementation note: use EPS only in this function
// usage note: check sign(x) < 0, sign(x) > 0, or sign(x) == 0
const double EPS = 1e-8;
int sign(double x) {
    if (x < -EPS) return -1;
    if (x > +EPS) return +1;
    return 0;
}

using real = long double;
struct point {
    real x, y;
    point(){}
    point(int X,int Y){x=X,y=Y;}
    point &operator+=(point p) { x += p.x; y += p.y; return *this; }
    point &operator-=(point p) { x -= p.x; y -= p.y; return *this; }
    point &operator*=(real a)     { x *= a;   y *= a;   return *this; }
    point &operator/=(real a)     { return *this *= (1.0/a); }
    point operator-() const    { return {-x, -y}; }
    bool operator<(point p) const {
        int s = sign(x - p.x);
        return s ? s < 0 : sign(y - p.y) < 0;
    }
};
bool operator==(point p, point q) { return !(p < q) && !(q < p); }
bool operator!=(point p, point q) { return p < q || q < p; }
bool operator<=(point p, point q) { return !(q < p); }
point operator+(point p, point q) { return p += q; }
point operator-(point p, point q) { return p -= q; }
point operator*(real a, point p) { return p *= a; }
point operator*(point p, real a) { return p *= a; }
point operator/(point p, real a) { return p /= a; }
real dot(point p, point q) { return p.x*q.x+p.y*q.y; }
real cross(point p, point q) { return p.x*q.y-p.y*q.x; } // left turn > 0
real norm2(point p) { return dot(p,p); }
point orth(point p) { return {-p.y, p.x}; }
real norm(point p) { return sqrt(dot(p,p)); }
real arg(point p) { return atan2(p.y, p.x); }
real arg(point p, point q){ return atan2(cross(p,q), dot(p,q)); }

istream &operator>>(istream &is, point &p) { is>>p.x>>p.y;return is; }
ostream &operator<<(ostream &os, const point &p) { os<<"("<<p.x<<","<<p.y<<")"; return os; }


// exact comparison by polar angle
// usage: sort(all(ps), polar_angle(origin, direction));
struct polar_angle {
    const point o;
    const int s; // +1 for ccw, -1 for cw
    polar_angle(point p = {0,0}, int s = +1) : o(p), s(s) { }
    int quad(point p) const {
        for (int i = 1; i <= 4; ++i, swap(p.x = -p.x, p.y))
            if (p.x > 0 && p.y >= 0) return i;
        return 0;
    }
    bool operator()(point p, point q) const {
        p = p - o; q = q - o;
        if (quad(p) != quad(q)) return s*quad(p) < s*quad(q);
        if (cross(p, q)) return s*cross(p, q) > 0;
        return norm2(p) < norm2(q); // closer first
    }
};

struct line { point p, q; };
bool operator==(line l, line m) {
    return !sign(cross(l.p-l.q,m.p-m.q)) && !sign(cross(l.p-l.q,m.p-l.p));
}

struct segment { point p, q; };
bool operator==(segment l, line m) {
    return (l.p==m.p && l.q==m.q) || (l.p==m.q && l.q==m.p); // do not consider the direction
}
struct circle { point p; real r; };
bool operator==(circle c, circle d) { return c.p == d.p && !sign(c.r - d.r); }

// inner tangent polygon.
// sometimes, circle problem can be reduced to discretized problem
vector<point> discretize(circle c, int n = 50) {
    vector<point> ps;
    for (int i = 0; i < n; ++i) {
        double x = cos(2*PI*i/n), y = sqrt(1 - x*x);
        ps.push_back(c.p + c.r * point({x,y}));
    }
    return ps;
}

typedef vector<point> polygon;


//-----------------------------------------------------------------------------
// visualizer
//-----------------------------------------------------------------------------
struct visualizer {
    real minx, maxx, miny, maxy, scale;
    ofstream ofs;
    visualizer(string s = "data.js") : ofs(s) {
        minx = miny =  1.0/0.0;
        maxx = maxy = -1.0/0.0;
    }
    void update(point p) {
        minx = min(minx, p.x); miny = min(miny, p.y);
        maxx = max(maxx, p.x); maxy = max(maxy, p.y);
        scale = 480/(max(maxx-minx, max(maxy-miny,1.0l)));
    }
    double X(point p) { return scale * (p.x-minx) + 10; }
    double Y(point p) { return 490 - scale * (p.y-miny); }
    vector<point> ps;
    vector<segment> ss;
    vector<circle> cs;
    visualizer &operator<<(circle c) {
        cs.push_back(c);
        update(c.p + point({ c.r, c.r}));
        update(c.p + point({-c.r,-c.r}));
        return *this;
    }
    visualizer &operator<<(point p) {
        ps.push_back(p);
        update(p);
        return *this;
    }
    visualizer &operator<<(segment s) {
        ss.push_back(s);
        update(s.p);
        update(s.q);
        return *this;
    }
    ~visualizer() {
        for (point p: ps)
            ofs << "circle(" << X(p) << "," << Y(p) << ",3.0)" << endl;
        for (segment s: ss)
            ofs << "line(" << X(s.p) << "," << Y(s.p) << ","
                << X(s.q) << "," << Y(s.q) << ")" << endl;
        for (circle c: cs)
            ofs << "circle(" << X(c.p) << "," << Y(c.p) << "," << scale*c.r << ")" << endl;
    }
};


//-----------------------------------------------------------------------------
// point p is on line l
//-----------------------------------------------------------------------------
vector<point> intersect(line l, point p) {
    if (sign(cross(l.p-p, l.q-p)) != 0) return {};
    return {p};
}
vector<point> intersect(point p, line l) {
    return intersect(l, p);
}

//-----------------------------------------------------------------------------
// point p is on segment s
//-----------------------------------------------------------------------------
vector<point> intersect(segment s, point p) {
    if (sign(cross(s.p-p, s.q-p)) != 0) return {};
    if (sign(  dot(s.p-p, s.q-p))  > 0) return {}; // >  for strict intersect
    return {p};                                    // >= for weak intersect
}
vector<point> intersect(point p, segment s) {
    return intersect(s, p);
}

//-----------------------------------------------------------------------------
// intersection of two lines
//
// Derivation: The crosspoint equation is
//   l.p + (l.q - l.p) t == m.p + (m.q - m.p) s ... (CP.1)
// Taking a cross product with (m.q - m.p), we have
//   (m.q - m.p) x (l.q - l.p) t == (m.q - m.p) x (m.p - l.p)
//   ~~~~~~~~~~~~a~~~~~~~~~~~~      ~~~~~~~~~~~~b~~~~~~~~~~~~
//
// If a != 0, these two lines have a proper crosspoint.
// If a == 0 and b == 0, these two lines are the same line.
// Otherwise, these two lines are parallel.
//-----------------------------------------------------------------------------
vector<point> intersect(line l, line m) {
    auto a = cross(m.q - m.p, l.q - l.p);
    auto b = cross(l.p - m.p, l.q - l.p);
    if ( sign(a)) return {m.p + b/a*(m.q - m.p)}; // properly crossing
    if (!sign(b)) return {m.p, m.q};              // same line
    return {};                                    // disjoint parallel
}

//-----------------------------------------------------------------------------
// intersection of line and segment
//
// In CP.1, t must be in [0, 1]. Thus 0 <= b/a <= 1 is required.
// By assuming a > 0, it is equivalent to b >= 0 and b-a <= 0
//-----------------------------------------------------------------------------
vector<point> intersect(line l, segment s) {
    auto a = cross(s.q - s.p, l.q - l.p);
    auto b = cross(l.p - s.p, l.q - l.p);
    if (a < 0) { a *= -1; b *= -1; }
    if (sign(b) < 0 || sign(a-b) < 0) return {};      // no intersect
    if (sign(a) != 0) return {s.p + b/a*(s.q - s.p)}; // properly crossing
    if (sign(b) == 0) return {s.p, s.q};              // same line
    return {};                                        // disjoint parallel
}

//-----------------------------------------------------------------------------
// intersection of two segments
//
// Solve two CP.1s simultaneously.
// If two segments are overlapping, it is bit difficult.
//-----------------------------------------------------------------------------
vector<point> intersect(segment s, segment t) {
    auto a = cross(s.q - s.p, t.q - t.p);
    auto b = cross(t.p - s.p, t.q - t.p);
    auto c = cross(s.q - s.p, s.p - t.p);
    if (a < 0) { a = -a; b = -b; c = -c; }
    if (sign(b) < 0 || sign(a-b) < 0 ||
        sign(c) < 0 || sign(a-c) < 0) return {};      // disjoint
    if (sign(a) != 0) return {s.p + b/a*(s.q - s.p)}; // properly crossing
    vector<point> ps;                                 // same line
    auto insert_if_possible = [&](point p) {
        for (auto q: ps) if (sign(dot(p-q, p-q)) == 0) return;
        ps.push_back(p);
    };
    if (sign(dot(s.p-t.p, s.q-t.p)) <= 0) insert_if_possible(t.p);
    if (sign(dot(s.p-t.q, s.q-t.q)) <= 0) insert_if_possible(t.q);
    if (sign(dot(t.p-s.p, t.q-s.p)) <= 0) insert_if_possible(s.p);
    if (sign(dot(t.p-s.q, t.q-s.q)) <= 0) insert_if_possible(s.q);
    return ps;
}

//-----------------------------------------------------------------------------
// reflected point with respect to l
//-----------------------------------------------------------------------------
point reflection(point p, line l) {
    auto a = dot(l.p-l.q, l.p-l.q);
    auto b = dot(l.p-p,   l.p-l.q);
    return 2 * (l.p + a/b*(l.q - l.p)) - p;
}

//-----------------------------------------------------------------------------
// closest point on l
//-----------------------------------------------------------------------------
point projection(point p, line l) {
    auto a = dot(l.p-l.q, l.p-l.q);
    auto b = dot(l.p-p,   l.p-l.q);
    return l.p + a/b*(l.q - l.p);
}

//-----------------------------------------------------------------------------
// closest point on s
//-----------------------------------------------------------------------------
point projection(point p, segment s) {
    auto a = dot(s.p-s.q, s.p-s.q);
    auto b = dot(s.p - p, s.p-s.q);
    if (sign(b)   < 0) return s.p;
    if (sign(a-b) < 0) return s.q;
    return s.p + b/a*(s.q - s.p);
}

//-----------------------------------------------------------------------------
// closest point on c
//-----------------------------------------------------------------------------
point projection(point p, circle c) {
    point v = p - c.p;
    return c.p + c.r * v / norm(v);
}
//-----------------------------------------------------------------------------
// distances
//-----------------------------------------------------------------------------
real dist(point p, point q) {
    return norm(p-q);
}
real dist(point p, line l) {
    return dist(p, projection(p, l));
}
real dist(line l, point p) {
    return dist(p, l);
}
real dist(line l, line m) {
    if (sign(cross(l.p-l.q,m.p-m.q))) return 0; // cross
    return dist(l.p, m);
}
real dist(point p, segment s) {
    return dist(p, projection(p, s));
}
real dist(line l, segment s) {
    if (intersect(l, s).size()) return 0;
    return min(dist(l, s.p), dist(l, s.q));
}
real dist(segment s, line l) {
    return dist(l, s);
}
real dist(segment s, segment T) {
    if (intersect(s, T).size()) return 0;
    return min({dist(s.p,T), dist(s.q,T), dist(T.p,s), dist(T.q,s)});
}


//-----------------------------------------------------------------------------
// intersection points of two circles
//-----------------------------------------------------------------------------
vector<point> intersect(circle c, circle d) {
    if (c.r < d.r) swap(c, d);
    auto pow2 = [](real a) { return a*a; };
    auto g = dot(c.p-d.p, c.p-d.p);
    if (sign(g) == 0) {
        if (sign(c.r-d.r) != 0) return {};
        return {{c.p.x+c.r, c.p.y}, {c.p.x, c.p.y+c.r}, {c.p.x-c.r, c.p.y}};
    }
    int inner = sign(g-pow2(c.r-d.r));
    int outer = sign(g-pow2(c.r+d.r));
    if (inner < 0 || outer > 0) return {};
    if (inner == 0) return {(c.r*d.p-d.r*c.p)/(c.r-d.r)};
    if (outer == 0) return {(c.r*d.p+d.r*c.p)/(c.r+d.r)};
    auto eta = (pow2(c.r) - pow2(d.r) + g)/(2*g);
    auto mu = sqrt(pow2(c.r)/g - pow2(eta));
    point q = c.p + eta*(d.p-c.p), v = mu*orth(d.p - c.p);
    return {q + v, q - v};
}

//-----------------------------------------------------------------------------
// intersection of line and circle
//-----------------------------------------------------------------------------
vector<point> intersect(line l, circle c) {
    point u = l.q - l.p, v = l.p - c.p;
    auto a = dot(u,u), b = dot(u,v)/a, t = (dot(v,v) - c.r*c.r)/a;
    auto det = b*b - t;
    if (sign(det) <  0) return {};          // no solution
    if (sign(det) == 0) return {l.p - b*u}; // touch inner/outer
    return {l.p - (b + sqrt(det))*u,        // properly intersect
            l.p - (b - sqrt(det))*u};
}
vector<point> intersect(circle c, line l) {
    return intersect(l, c);
}

//-----------------------------------------------------------------------------
// intersection of segment and circle
// number of points:
//   0 ==> no intersect
//   1 ==> touch
//   2 ==> contained
//   3 ==> penetrating single side
//   4 ==> penetrating both sides
// sorted from s.p to s.q; usually, one would use ans[0] and ans.back().
//-----------------------------------------------------------------------------
vector<point> intersect(circle c, segment s) {
    point u = s.q - s.p, v = s.p - c.p;
    auto a = dot(u,u), b = dot(u,v)/a, t = (dot(v,v) - c.r*c.r)/a;
    auto det = b*b - t;
    if (sign(det) <  0) return {};          // no solution

    auto t1 = -b - sqrt(det), t2 = -b + sqrt(det);
    vector<point> ps;
    auto insert_if_possible = [&](point p) {
        for (auto q: ps) if (sign(dot(p-q, p-q)) == 0) return;
        ps.push_back(p);
    };
    if (sign(c.r - norm(s.p-c.p))   >= 0) insert_if_possible(s.p);
    if (sign(t1) >= 0 && sign(1-t1) >= 0) insert_if_possible(s.p+t1*u);
    if (sign(t2) >= 0 && sign(1-t2) >= 0) insert_if_possible(s.p+t2*u);
    if (sign(c.r - norm(s.q-c.p))   >= 0) insert_if_possible(s.q);
    return ps;
}
vector<point> intersect(segment s, circle c) {
    return intersect(c, s);
}
bool contains(circle c, point p) {
    return sign(dot(c.p-p, c.p-p) - c.r * c.r) <= 0;
}


//-----------------------------------------------------------------------------
// polygon contains a point
// half-line crossing method
//-----------------------------------------------------------------------------
int contains(polygon ps, point p) {
    bool in = false;
    for (int i = 0; i < ps.size(); ++i) {
        int j = (i+1 == ps.size() ? 0 : i+1);
        point a = ps[i] - p, b = ps[j] - p;
        if (a.y > b.y) swap(a, b);
        if (a.y <= 0 && 0 < b.y && cross(a, b) < 0) in = !in;
        if (!sign(cross(a, b)) && sign(dot(a, b)) <= 0)
            return 1; // point on the edge
    }
    return in ? 2 : 0; // point in:out the polygon
}

//-----------------------------------------------------------------------------
// convex hull with the given points
//
// Andrew's monotone chain
//
// [verified]
//
// A. M. Andrew (1979):
// Another efficient algorithm for convex hulls in two dimensions.
// Information Processing Letters 9 (5): 216-219.
//-----------------------------------------------------------------------------
polygon convex_hull(vector<point> ps) {
    int n = ps.size(), k = 0;
    sort(all(ps));
    vector<point> ch(2*n);
    auto cond = [&](point p, point q, point o) {
        int a = sign(cross(p-o, q-o)); // return a < 0 if no three points on line
        return a ? a < 0 : sign(dot(p-o, q-o)) >= 0;
    };
    for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
        for (; k >= 2 && cond(ch[k-2], ch[k-1], ps[i]); --k);
    for (int i = n-2, t = k+1; i >= 0; ch[k++] = ps[i--]) // upper-hull
        for (; k >= t && cond(ch[k-2], ch[k-1], ps[i]); --k);
    ch.resize(k-1);
    return ch;
}


//-----------------------------------------------------------------------------
// farthest pair of points
//
// is located on the convex hull. perform rotating caliper.
//
// [verified ACAC002]
//-----------------------------------------------------------------------------
pair<point,point> farthest_pair(vector<point> ps) {
    vector<point> ch = convex_hull(ps);
    int n = ch.size();
    int u = 0, v = 1;
    real best = -1;
    for (int i = 0, j = 1; i < n; ++i) {
        while (1) {
            int k = (j+1 < n ? j+1 : 0);
            real len = norm2(ch[j] - ch[i]);
            if (sign(len - norm2(ch[k] - ch[i])) <= 0) j = k;
            else {
                if (best < len) { best = len; u = i; v = j; }
                break;
            }
        }
    }
    return make_pair(ch[u], ch[v]);
}


//-----------------------------------------------------------------------------
// signed area of arbitrary polygon
//
// [verified]
//-----------------------------------------------------------------------------
real area(polygon ps) {
    if (ps.size() <= 2) return 0;
    auto a = cross(ps.back(), ps[0]);
    for (int i = 0; i+1 < ps.size(); ++i)
        a += cross(ps[i], ps[i+1]);
    return a/2;
}

//-----------------------------------------------------------------------------
// left side of a convex polygon with respect to a line
//
// [verified]
//-----------------------------------------------------------------------------
polygon convex_cut(polygon ps, line l) {
    vector<point> qs;
    for (int i = 0; i < ps.size(); ++i) {
        int j = (i+1 == ps.size() ? 0 : i+1);
        if (sign(cross(l.p - ps[i], l.q - ps[i])) >= 0) qs.push_back(ps[i]);
        if (sign(cross(l.p - ps[i], l.q - ps[i])) *
            sign(cross(l.p - ps[j], l.q - ps[j])) < 0) {
            auto a = cross(ps[j] - ps[i], l.q - l.p);
            auto b = cross(l.p - ps[i], l.q - l.p);
            qs.push_back(ps[i] + b/a*(ps[j] - ps[i]));
        }
    }
    return qs;
}

//-----------------------------------------------------------------------------
// the circle through three points
//-----------------------------------------------------------------------------
circle three_point_circle(point p, point q, point r) {
    point u = orth(q - p), v = r - p;
    point o = (p+q + u*dot(r-q,v)/dot(u,v))/2;
    return {o, norm(p-o)};
}
//-----------------------------------------------------------------------------
// area of quadrilateral;
// not verified
//-----------------------------------------------------------------------------
real quadrilateral_area(real a, real b, real c, real d) {
    real s = a+b+c+d;
    return sqrt((s-a)*(s-b)*(s-c)*(s-d))/4;
}
real triangle_area(real a, real b, real c) {
    return quadrilateral_area(a, b, c, 0);
}
real excircle_radius(real a, real b, real c) {
    return a*b*c/4/triangle_area(a, b, c);
}
real incircle_radius(real a, real b, real c) {
    return 2*triangle_area(a,b,c)/(a+b+c);
}

//-----------------------------------------------------------------------------
// tangent line of a circle at the nearest point from p
//
// Let q be a tangent point.
// The angle between q -- p -- c.p is
//   sin(t) = r/|p - c.p|.
// and the solution is
//   p + (c.p - p) * exp(\pm it).
//
// [verified]
//-----------------------------------------------------------------------------
vector<line> tangent(point p, circle c) {
    point u = p - c.p, v = orth(u);
    auto g = dot(u,u) - c.r*c.r;
    if (sign(g) < 0) return {};
    if (sign(g) == 0) return {{p, p + v}};
    u = u * (c.r*c.r/dot(u,u));
    v = v * (c.r*sqrt(g)/dot(v,v));
    return {{p, c.p + u - v}, {p, c.p + u + v}};
}
vector<line> tangent(circle c, point p) {
    return tangent(p, c);
}

//-----------------------------------------------------------------------------
// common tangents of two circles
//
// [verified]
//-----------------------------------------------------------------------------
vector<line> tangent(circle c, circle d) {
    if (c.r < d.r) swap(c, d);
    auto g = dot(c.p-d.p, c.p-d.p);
    if (sign(g) == 0) return {}; // same origin
    point u = (d.p-c.p)/sqrt(g), v = orth(u); // coordinate systems
    vector<line> ls;
    for (int s = +1; s >= -1; s -= 2) {
        auto h = (c.r+s*d.r)/sqrt(g); // = cos(theta)
        if (sign(1 - h*h) == 0) { // touch inner/outer
            ls.push_back({c.p+c.r*u, c.p+c.r*(u+v)});
        } else if (sign(1 - h*h) > 0) { // properly intersect
            point uu = h*u, vv = sqrt(1-h*h)*v;
            ls.push_back({c.p+c.r*(uu+vv), d.p-d.r*(uu+vv)*s});
            ls.push_back({c.p+c.r*(uu-vv), d.p-d.r*(uu-vv)*s});
        }
    }
    return ls;
}

//-----------------------------------------------------------------------------
// common tangent circles of two lines of radius r
//
//   o|o
//  --+--
//   o|o
//
// number of solutions:
//   0: parallel and distance < r
//   1: parallel and distance = r
//   4: non-parallel
//
// [non-verified]
//-----------------------------------------------------------------------------
vector<circle> tangent_circles(line l, line m, real r) {
    vector<circle> cs;
    real a = cross(l.p-m.p, l.q-l.p), b = cross(m.q-m.p, l.q-l.p);
    if (!sign(b)) { // parallel case
        if (l.q < l.p) swap(l.p, l.q);
        if (m.q < m.p) swap(m.p, m.q);
        if (sign(cross(m.p-l.p, m.q-l.p)) >= 0) swap(l, m); // l is lower
        point v = orth(m.q - m.p); v /= norm(v);
        real d = a / cross(l.q - l.p, v);
        if (sign(d - 2*r) == 0) cs.push_back({l.p + r * v, r});
    } else {
        point o = m.p + a/b * (m.q - m.p), u = l.q - l.p, v = m.q - m.p;
        u /= norm(u); v /= norm(v);
        for (int i = 0; i < 4; ++i) {
            point w = u + v; w /= norm(w);
            real t = r / sqrt(1 - dot(v,w)*dot(v,w));
            cs.push_back({o + t * w, r});
            u *= -1; swap(u, v);
        }
    }
    return cs;
}

//-----------------------------------------------------------------------------
// find a line that passes the maximum number of points
//
// [non-verified]
//-----------------------------------------------------------------------------
int maximum_points_line(vector<point> ps) {
    sort(all(ps)); // assume dx >= 0; if dx == 0 then dy >= 0
    int max_count = 0;
    for (int i = 0; i < ps.size(); ++i) {
        vector<point> qs;
        int base = 1;
        for (int j = 0; j < i; ++j)
            if (ps[j] == ps[i]) ++base;
            else qs.push_back(ps[j] - ps[i]);
        sort(all(qs), polar_angle());
        for (int j = 0, k; j < qs.size(); j += k) {
            for (k = 1; j+k < qs.size() && sign(cross(qs[j], qs[j+k])) == 0; ++k);
            max_count = max(max_count, base + k);
        }
    }
    return max_count;
}

// for comparison
int maximum_points_line_n(vector<point> ps) {
    sort(all(ps));
    int ans = 0;
    for (int i = 0; i < ps.size(); ++i) {
        for (int j = i+1; j < ps.size(); ++j) {
            if (ps[i] == ps[j]) continue;
            int count = 0;
            for (int k = 0; k < ps.size(); ++k) {
                if (intersect((line){ps[i], ps[j]}, ps[k]).size() > 0) ++count;
            }
            ans = max(ans, count);
        }
    }
    return ans;
}
void verify_maximum_points_line() {
    int n = 100;
    vector<point> ps(n);
    for (int i = 0; i < n; ++i) {
        ps[i].x = rand() % 20;
        ps[i].y = rand() % 20;
    }
    cout << maximum_points_line(ps) << endl;
    cout << maximum_points_line_n(ps) << endl;
}


//-----------------------------------------------------------------------------
// triangulate simple polygon in O(n) time.
//
// [non-verified]; future work for polygonal overlay
//-----------------------------------------------------------------------------
real triangulate(vector<point> ps) {
    int n = ps.size();
    vector<int> next(n);
    for (int i = 0; i < n-1; ++i) next[i] = i+1;
    auto is_ear = [&](int i, int j, int k) {
        if (sign(cross(ps[j]-ps[i], ps[k]-ps[i])) <= 0) return false;
        for (int l = next[k]; l != i; l = next[l])
            if (sign(cross(ps[i]-ps[l], ps[j]-ps[l])) >= 0
                && sign(cross(ps[j]-ps[l], ps[k]-ps[l])) >= 0
                && sign(cross(ps[k]-ps[l], ps[i]-ps[l])) >= 0) return false;
        return true;
    };
    real area = 0;
    for (int i = 0; next[next[i]] != i; ) {
        if (is_ear(i, next[i], next[next[i]])) {
            area  += abs(cross(ps[next[i]]-ps[i], ps[next[next[i]]] - ps[i])) / 2;
            next[i] = next[next[i]];
        } else i = next[i];
    }
    return area;
}

//-----------------------------------------------------------------------------
// area of intersection of two circles
// [verified]
//-----------------------------------------------------------------------------
real intersection_area(circle c, circle d) {
    if (c.r < d.r) swap(c, d);
    auto A = [&](real r, real h) {
        return r*r*acos(h/r)-h*sqrt(r*r-h*h);
    };
    auto l = norm(c.p - d.p), a = (l*l + c.r*c.r - d.r*d.r)/(2*l);
    if (sign(l - c.r - d.r) >= 0) return 0; // far away
    if (sign(l - c.r + d.r) <= 0) return PI*d.r*d.r;
    if (sign(l - c.r) >= 0) return A(c.r, a) + A(d.r, l-a);
    else return A(c.r, a) + PI*d.r*d.r - A(d.r, a-l);
}
//-----------------------------------------------------------------------------
// circle-polygon intersection area
// [verified]
//-----------------------------------------------------------------------------
real intersection_area(vector<point> ps, circle c) {
    auto tri = [&](point p, point q){
        point d = q - p;
        auto a = dot(d,p)/dot(d,d), b = (dot(p,p)-c.r*c.r)/dot(d,d);
        auto det = a*a - b;
        if (det <= 0) return arg(p,q) * c.r*c.r / 2;
        auto s = max(0.l, -a-sqrt(det)), t = min(1.l, -a+sqrt(det));
        if (t < 0 || 1 <= s) return c.r*c.r*arg(p,q)/2;
        point u = p + s*d, v = p + t*d;
        return arg(p,u)*c.r*c.r/2 + cross(u,v)/2 + arg(v,q)*c.r*c.r/2;
    };
    auto sum = 0.0;
    for (int i = 0; i < ps.size(); ++i)
        sum += tri(ps[i] - c.p, ps[(i+1)%ps.size()] - c.p);
    return sum;
}
real intersection_area(circle c, vector<point> ps) {
    return intersection_area(ps, c);
}

//-----------------------------------------------------------------------------
// find the closest pair of points by sweepline
// [verified]
//-----------------------------------------------------------------------------
pair<point,point> closest_pair(vector<point> ps) {
    sort(all(ps), [](point p, point q) { return p.y < q.y; });
    auto u = ps[0], v = ps[1];
    auto best = dot(u-v, u-v);
    auto update = [&](point p, point q) {
        auto dist = dot(p-q, p-q);
        if (best > dist) { best = dist; u = p; v = q; }
    };
    set<point> S; S.insert(u); S.insert(v);
    for (int l = 0, r = 2; r < ps.size(); ++r) {
        if (S.count(ps[r])) return {ps[r], ps[r]};
        if ((ps[l].y-ps[r].y)*(ps[l].y-ps[r].y) > best) S.erase(ps[l++]);
        auto i = S.insert(ps[r]).fst;
        for (auto j = i; ; ++j) {
            if (j == S.end() || (i->x-j->x)*(i->x-j->x) > best) break;
            if (i != j) update(*i, *j);
        }
        for (auto j = i; ; --j) {
            if (i != j) update(*i, *j);
            if (j == S.begin() || (i->x-j->x)*(i->x-j->x) > best) break;
        }
    }
    return {u, v};
}
//-----------------------------------------------------------------------------
// find the closest pair of points by divide and conquer
// (slower than the sweepline)
//-----------------------------------------------------------------------------
pair<point,point> closest_pair2(vector<point> ps) {
    sort(all(ps), [](point p, point q) { return p.y < q.y; });
    auto u = ps[0], v = ps[1];
    auto best = dot(u-v, u-v);
    auto update = [&](point p, point q) {
        auto dist = dot(p-q, p-q);
        if (best > dist) { best = dist; u = p; v = q; }
    };
    function<void(int,int)> rec = [&](int l, int r) {
        if (r - l <= 1) {
            for (int i = l; i < r; ++i)
                for (int j = i+1; j < r; ++j)
                    update(ps[i], ps[j]);
            stable_sort(&ps[l], &ps[r]);
        } else {
            int m = (l + r) / 2;
            auto y = ps[m].y;
            rec(l, m); rec(m, r);
            inplace_merge(&ps[l], &ps[m], &ps[r]);
            vector<point> qs;
            for (int i = l; i < r; ++i) {
                if ((ps[i].y-y)*(ps[i].y-y) >= best) continue;
                for (int j = (int)qs.size()-1; j >= 0; --j) {
                    if ((qs[j].x-ps[i].x)*(qs[j].x-ps[i].x) >= best) break;
                    update(qs[j], ps[i]);
                }
                qs.push_back(ps[i]);
            }
        }
    };
    rec(0, ps.size());
    return {u, v};
}


//-----------------------------------------------------------------------------
// half-plane intersection in O(n log n)
// [un-verified; buggy?]
//-----------------------------------------------------------------------------
vector<point> half_plane_intersection(vector<line> ls) {
    int n = ls.size();
    sort(all(ls), [&](line l, line m) { return arg(l.p-l.q) < arg(m.p-m.q); });
    int L = 0, R = 0;
    vector<line> bd(2*n);
    vector<point> ps(2*n);
    bd[R] = ls[0];
    auto left = [&](point p, line l) { return sign(cross(l.p-p, l.q-p)) >= 0; };
    for (int i = 1; i < n; ++i) {
        if (!sign(cross(bd[R].p-bd[R].q, ls[i].p-ls[i].q))) {
            if (left(ls[i].p, bd[R])) bd[R] = ls[i];
        } else {
            while (L < R && !left(ps[R-1], ls[i])) --R;
            while (L < R && !left(ps[L]  , ls[i])) ++L;
            bd[++R] = ls[i];
        }
        if (R > L) ps[R-1] = intersect(bd[R-1], bd[R])[0];
    }
    while (L < R && !left(ps[R-1], bd[L])) --R;
    if (R - L <= 1) return {};
    if (R > L) ps[R] = intersect(bd[L], bd[R])[0];
    vector<point> ch = {ps[L]};
    for (int i = L+1; i <= R; ++i)
        if (!(ch.back() == ps[i])) ch.push_back(ps[i]);
    if (ch.size() > 1 && ch.back() == ch[0]) ch.pop_back();
    return ch;
}



//-----------------------------------------------------------------------------
// geometric median, i.e., p in argmin sum |ps[i] - p|_2
//
// Weiszfield's iterative reweighted method least squares
// with avoiding equal points
// [verified: LA5102]
//-----------------------------------------------------------------------------
point geometric_median(vector<point> ps) {
    point g = {0,0};
    real eta = 1000.0;
    for (int iter = 0; iter < 1000000; ++iter, eta /= 2) {
        real w = 0;
        point h = {0,0};
        for (point p: ps) {
            real a = eta + norm(p - g);
            h = h + p/a; w = w + 1/a;
        }
        h = h / w; swap(g, h);
        if (norm(g - h) < EPS) break;
    }
    return g;
}


//-----------------------------------------------------------------------------
// find a circle of radius r that contains many points as possible
//
// quad-tree search (this is faster than the next sweepline solution)
// [verified: AOJ 1132]
//-----------------------------------------------------------------------------
int maximum_circle_cover(vector<point> ps, double r) {
    const double dx[] = {1,-1,-1,1}, dy[] = {1,1,-1,-1};
    point best_p;
    int best = 0;
    function<void(point,double,vector<point>)>
            rec = [&](point p, double w, vector<point> ps) {
        w /= 2;
        point qs[4];
        vector<point> pss[4];
        for (int i = 0; i < 4; ++i) {
            qs[i] = p + w * point({dx[i], dy[i]});
            int lo = 0;
            for (point q: ps) {
                auto d = dist(qs[i], q);
                if (sign(d - r) <= 0) ++lo;
                if (sign(d - w*sqrt(2) - r) <= 0) pss[i].push_back(q);
            }
            if (lo > best) { best = lo; best_p = qs[i]; }
        }
        for (int i = 0, j; i < 4; ++i) {
            for (int j = i+1; j < 4; ++j)
                if (pss[i].size() < pss[j].size())
                    swap(pss[i], pss[j]), swap(qs[i], qs[j]);
            if (pss[i].size() <= best) break;
            rec(qs[i], w, pss[i]);
        }
    };
    real w = 0;
    for (point p: ps) w = max(w, max(abs(p.x), abs(p.y)));
    rec({0,0}, w, ps);
    return best; //best_p;
}

//-----------------------------------------------------------------------------
// find a circle of radius r that contains many points as possible
//
// sweepline O(n^2 log n).
// [verified: AOJ 1132]
//-----------------------------------------------------------------------------
int maximum_circle_cover2(vector<point> ps, double r) {
    int best = 0;
    for (point p: ps) {
        int count = 0;
        vector<pair<double,int>> aux;
        for (point q: ps) {
            auto d = dist(p, q);
            if (sign(d) == 0) ++count;
            else if (sign(d - 2*r) <= 0) {
                auto theta = arg(q-p);
                auto phi   = acos(min(1.l, d/(2*r)));
                aux.push_back({theta-phi, -1});
                aux.push_back({theta+phi, +1});
            }
        }
        sort(all(aux));
        best = max(best, count);
        for (auto a: aux)
            best = max(best, count -= a.snd);
    }
    return best;
}

int main()
{
    int n;
    cin>>n;
    vector<point> vec;
    long double ans=1e9;
    for (int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        vec.push_back(point(x,y));
    }
    long double l = 1e-6, r = 1e5;
    for (int i=0;i<300;i++) {
        long double mid = (l+r)/2;
        if (maximum_circle_cover2(vec, mid) == vec.size())ans=mid,r=mid;
        else l=mid;
    }
    cout<<setprecision(10)<<fixed<<ans<<endl;
}

Measured memory_bytes: 256