#include <bits/stdc++.h>
#define rep(a, b, c) for (int a = b; a <= c; a++)
#define ALL(x) (x).begin(), (x).end()
#define IOS cin.tie(0)->sync_with_stdio(false)
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) 42
#endif
#define OPENSTACK
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;
typedef double db;
constexpr db inf = 1e20;
constexpr db eps = 1e-8;
const db pi = acos(-1);
constexpr int sgn(db x) { return x < -eps ? -1 : x > eps; }
constexpr int cmp(db x, db y) { return sgn(x - y); }
struct Point {
    db x, y;
    constexpr Point(db _x = 0, db _y = 0) : x(_x), y(_y) {}
    constexpr Point operator+() const noexcept { return *this; }
    constexpr Point operator-() const noexcept { return Point(-x, -y); }
    constexpr Point operator+(const Point& p) const
    {
        return Point(x + p.x, y + p.y);
    }
    constexpr Point operator-(const Point& p) const
    {
        return Point(x - p.x, y - p.y);
    }
    constexpr Point operator*(const db& k) { return Point(x * k, y * k); }
    constexpr Point operator/(const db& k) { return Point(x / k, y / k); }
    constexpr Point& operator+=(const Point& p)
    {
        return x += p.x, y += p.y, *this;
    }
    constexpr Point& operator-=(const Point& p)
    {
        return x -= p.x, y -= p.y, *this;
    }
    constexpr Point& operator*=(const db& k) { return x *= k, y *= k, *this; }
    constexpr Point& operator/=(const db& k) { return x /= k, y /= k, *this; }
    constexpr bool operator==(const Point& r) const noexcept
    {
        return cmp(x, r.x) == 0 and cmp(y, r.y) == 0;
    }
    constexpr bool operator<(const Point& r) const noexcept
    {
        return sgn(x - r.x) == 0 ? sgn(y - r.y) < 0 : x < r.x;
    }
    friend istream& operator>>(istream& is, Point& p) { return is >> p.x >> p.y; }
    friend ostream& operator<<(ostream& os, Point p)
    {
        return os << "(" << p.x << ", " << p.y << ")";
    }
    constexpr db dot(const Point& r) const { return x * r.x + y * r.y; }
    constexpr db cross(const Point& r) const { return x * r.y - y * r.x; }
    constexpr int quad() const
    {
        return sgn(y) > 0 || (sgn(y) == 0 && sgn(x) > 0) ? 1 : -1;
    }
    constexpr bool arg_cmp(const Point& r) const
    {
        int L = (*this).quad(), R = r.quad();
        if (L != R) return L < R;
        db X = x * r.y, Y = r.x * y;
        if (X != Y) return X > Y;
        return x < r.x;
    }
};
db dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
db cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
db square(Point p) { return dot(p, p); }
db len(Point p) { return sqrt(db(square(p))); }
Point unit(Point p) { return p / len(p); }
db arg(Point p) { return atan2(p.y, p.x); }
Point polar(db r, db theta) { return Point(cos(theta) * r, sin(theta) * r); }
Point rotleft(Point p) { return Point(-p.y, p.x); }
Point rotright(Point p) { return Point(p.y, -p.x); }
Point rotate(Point p, Point r, db angle)
{
    Point v = p - r;
    db c = cos(angle), s = sin(angle);
    return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
}
// 1 : left, 0 : same, -1 : right
int toleft(Point a, Point b, Point c) { return sgn(cross(b - a, c - a)); }
int toleft(Point a, Point b) { return sgn(cross(a, b)); }
//(0,0) in negative plane
int quad(Point p)
{
    return sgn(p.y) > 0 || (sgn(p.y) == 0 && sgn(p.x) > 0) ? 1 : -1;
}
bool arg_cmp(const Point& l, const Point& r) { return l.arg_cmp(r); }
db distance(const Point& a, const Point& b) { return len(a - b); }
struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
    Line(Point p, db angle)
    {
        a = p;
        if (cmp(angle, pi / 2) == 0)
            b = (a + Point(0, 1));
        else
            b = (a + Point(1, tan(angle)));
    }
    // ax + by + c = 0
    Line(db A, db B, db C)
    {
        if (sgn(A) == 0)
            a = Point(0, -C / B), b = Point(1, -C / B);
        else if (sgn(B) == 0)
            a = Point(-C / A, 0), b = Point(-C / A, 1);
        else
            a = Point(0, -C / B), b = Point(-C / A, 0);
    }
};
struct Segment : Line {
    Segment() = default;
    Segment(Point a, Point b) : Line(a, b) {}
};
db len(const Line& l) { return len(l.b - l.a); }
int toleft(Point p, Line l) { return sgn(cross(l.b - l.a, p - l.a)); }
bool parallel(Line l1, Line l2)
{
    return sgn(cross(l1.b - l1.a, l2.b - l2.a)) == 0;
}
bool orthogonal(const Line& l1, const Line& l2)
{
    return sgn(dot(l1.a - l1.b, l2.a - l2.b)) == 0;
}
#define crossOp(a, b) sgn(cross(a, b))
#define dotOp(a, b) sgn(dot(a, b))
// 两直线弧度
db rad(const Line& l1, const Line& l2)
{
    return atan2(fabs(cross(l1.b - l1.a, l2.b - l2.a)),
        dot(l1.b - l1.a, l2.b - l2.a));
}
// 返回直线倾斜角 0<=angle<π
db angle(const Line& l)
{
    db k = atan2(l.b.y - l.a.y, l.b.x - l.a.x);
    if (sgn(k) < 0) k += pi;
    if (sgn(k - pi) == 0) k -= pi;
    return k;
}
db distancePL(const Point& p, const Line& l)
{
    return fabs(cross(l.b - l.a, p - l.a)) / len(l);
}
db distancePS(const Point& p, const Segment& l)
{
    if (sgn(dot(p - l.a, l.b - l.a)) < 0) return distance(p, l.a);
    if (sgn(dot(p - l.b, l.a - l.b)) < 0) return distance(p, l.b);
    return distancePL(p, l);
}
int pointonsegment(Point a, Point b, Point c)
{
    b = b - a, c = 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;          // "ONLINE_BACK"
    if (square(b) < square(c)) return -2;  // "ONLINE_FRONT"
    return 0;                              // "ON_SEGMENT"
}
bool intersect(const Point& p, const Line& l)
{
    return abs(pointonsegment(l.a, l.b, p)) != 1;
}
bool intersect(const Point& p, const Segment& s)
{
    return pointonsegment(s.a, s.b, p) == 0;
}
bool intersect(const Line& l, const Line& m) { return !parallel(l, m); }
bool intersect(const Line& l, const Segment& s)
{
    return crossOp(l.b - l.a, s.a - l.a) * crossOp(l.b - l.a, s.b - l.a) <= 0;
}
bool intersect(const Segment& s, const Segment& t)
{
    return pointonsegment(s.a, s.b, t.a) * pointonsegment(s.a, s.b, t.b) <= 0 &&
        pointonsegment(t.a, t.b, s.a) * pointonsegment(t.a, t.b, s.b) <= 0;
}
db distanceSS(const Segment& l, const Segment& m)
{
    if (intersect(l, m)) return 0.0;
    return min({ distancePS(l.a, m), distancePS(l.b, m), distancePS(m.a, l),
                distancePS(m.b, l) });
}
// 2 规范相交 1 非规范相交 0 不相交
int crossSS(Segment l, Segment m)
{
    int d1 = toleft(m.a, l);
    int d2 = toleft(m.b, l);
    int d3 = toleft(l.a, m);
    int d4 = toleft(l.b, m);
    if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 2;
    return (d1 == 0 && intersect(m.a, l)) || (d2 == 0 && intersect(m.b, l)) ||
        (d3 == 0 && intersect(l.a, m)) || (d4 == 0 && intersect(l.b, m));
}
// 2 规范相交 1 非规范相交 0 不相交
int crossLS(Line l, Segment m)
{
    int d1 = toleft(m.a, l);
    int d2 = toleft(m.b, l);
    if ((d1 ^ d2) == -2) return 2;
    return (d1 == 0 || d2 == 0);
}
// 0 平行 1 重合 2 相交
int crossLL(Line l, Line m)
{
    if (parallel(l, m)) return intersect(l.a, m);
    return 2;
}
Point crosspointLL(const Line& l, const Line& m)
{
    db A = cross(l.b - l.a, m.b - m.a);
    db B = cross(l.b - l.a, l.b - m.a);
    if (sgn(A) == 0 and sgn(B) == 0) return m.a;
    return m.a + (m.b - m.a) * (B / A);
}
// 点到直线投影点
Point projection(const Point& p, const Line& l)
{
    db t = dot(p - l.a, l.a - l.b) / square(l.a - l.b);
    return l.a + (l.a - l.b) * t;
}
// 直线对称点
Point symmetrypoint(const Point& p, const Line& l)
{
    Point q = projection(p, l);
    return Point(2 * q.x - p.x, 2 * q.y - p.y);
}
using P = Point;
using Points = vector<P>;
using Polygon = Points;
// 周长
db perimeter(const Polygon& p)
{
    db res = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) res += len(p[i] - p[(i + 1) % n]);
    return res;
}
// 面积两倍
db area2(const Polygon& p)
{
    db res = 0;
    int n = p.size();
    for (int i = 0; i < n; i++) res += cross(p[i], p[(i + 1) % n]);
    return res;
}
// 凸性判定 逆时针给出点
bool is_convex(const Polygon& p)
{
    int n = (int) p.size();
    for (int i = 0; i < n; i++) {
        if (pointonsegment(p[(i + n - 1) % n], p[i], p[(i + 1) % n]) == -1)
            return false;
    }
    return true;
}

enum { OUT, ON, IN };
// 2 contains 1 on segment 0 out
int pointInPolygon(const Point& a, const Polygon& p)
{
    int n = p.size();
    for (int i = 0; i < n; i++) {
        if (intersect(a, Segment(p[i], p[(i + 1) % n]))) return ON;
    }
    int t = 0;
    for (int i = 0; i < n; i++) {
        auto u = p[i];
        auto v = p[(i + 1) % n];
        if (cmp(u.x, a.x) == -1 && cmp(v.x, a.x) >= 0 &&
            toleft(a, Line(v, u)) > 0) {
            t ^= 1;
        }
        if (cmp(u.x, a.x) >= 0 && cmp(v.x, a.x) == -1 &&
            toleft(a, Line(u, v)) > 0) {
            t ^= 1;
        }
    }
    return t == 1 ? IN : OUT;
}
// 凸多边形log求包含点问题
int pointInconvexPolygonlog(const Point& p, const Polygon& Q)
{
    int N = (int) Q.size();
    Point g = (Q[0] + Q[N / 3] + Q[N * 2 / 3]) / 3.0;
    if (g == p) return IN;
    Point gp = p - g;
    int l = 0, r = N;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        Point gl = Q[l] - g;
        Point gm = Q[mid] - g;
        if (cross(gl, gm) > 0) {
            if (cross(gl, gp) >= 0 && cross(gm, gp) <= 0)
                r = mid;
            else
                l = mid;
        }
        else {
            if (cross(gl, gp) <= 0 && cross(gm, gp) >= 0)
                l = mid;
            else
                r = mid;
        }
    }
    r %= N;
    db v = cross(Q[l] - p, Q[r] - p);
    return sgn(v) == 0 ? ON : sgn(v) == -1 ? OUT : IN;
}
bool segmentInPolygon(const Segment& s, const Polygon& p)
{
    auto [a, b] = s;
    if (pointInPolygon(a, p) == 0 || pointInPolygon(b, p) == 0) return false;
    int n = p.size();
    Polygon q;
    for (int i = 0; i < n; i++) {
        auto l = Segment(p[i], p[(i + 1) % n]);
        if (crossSS(s, l) == 2) return false;
        if (intersect(a, l))
            q.push_back(a);
        else if (intersect(b, l))
            q.push_back(b);
        else if (intersect(p[i], l))
            q.push_back(p[i]);
    }
    sort(q.begin(), q.end());
    for (int i = 0; i + 1 < q.size(); i++) {
        if (pointInPolygon((q[i] + q[i + 1]) / 2, p) == 0) return false;
    }
    return true;
}
bool intersect(const Polygon& ps, const Polygon& qs)
{
    int pl = ps.size(), ql = qs.size(), i = 0, j = 0;
    while ((i < pl or j < ql) and (i < 2 * pl) and (j < 2 * ql)) {
        auto ps0 = ps[(i + pl - 1) % pl], ps1 = ps[i % pl];
        auto qs0 = qs[(j + ql - 1) % ql], qs1 = qs[j % ql];
        if (intersect(Segment(ps0, ps1), Segment(qs0, qs1))) return true;
        Point a = ps1 - ps0;
        Point b = qs1 - qs0;
        db v = cross(a, b);
        db va = cross(qs1 - qs0, ps1 - qs0);
        db vb = cross(ps1 - ps0, qs1 - ps0);
        if (!v and va < 0 and vb < 0) return false;
        if (!v and !va and !vb) {
            i += 1;
        }
        else if (v >= 0) {
            if (vb > 0)
                i += 1;
            else
                j += 1;
        }
        else {
            if (va > 0)
                j += 1;
            else
                i += 1;
        }
    }
    return false;
}
// 凸包
Polygon getHull(Polygon p)
{
    Polygon h, l;
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    if (p.size() <= 1) return p;
    for (auto a : p) {
        //<= >= 弹出共线点 < >不弹出共线点
        while (h.size() > 1 && cross(a - h.back(), a - h[h.size() - 2]) <= 0)
            h.pop_back();
        while (l.size() > 1 && cross(a - l.back(), a - l[l.size() - 2]) >= 0)
            l.pop_back();
        l.push_back(a);
        h.push_back(a);
    }
    l.pop_back();
    reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    return l;
}
// 平面割 返回l左侧的多边形，凸多边形
Polygon convex_cut(const Polygon& a, const Line& l)
{
    Polygon ret;
    int n = a.size();
    for (int i = 0; i < n; i++) {
        const Point& now = a[i];
        const Point& nxt = a[(i + 1) % n];
        auto cf = toleft(now, l);
        auto cs = toleft(nxt, l);
        if (cf >= 0) {
            ret.emplace_back(now);
        }
        if (cf * cs < 0) {
            ret.emplace_back(crosspointLL(Line(now, nxt), l));
        }
    }
    return ret;
}
// 最远点对(旋转卡壳)凸多边形 如果存在三点共线 先求凸包弹出共线点 不然在大小3的时候 会死循环
db rotatingCalipers(Polygon a)
{
    int n = a.size();
    if (n <= 2) return distance(a[0], a[1]);
    int i = 0, j = 0;
    for (int k = 0; k < n; k++) {
        if (a[k] < a[i]) i = k;
        if (a[j] < a[k]) j = k;
    }
    db res = 0;
    int si = i, sj = j;
    while (i != sj || j != si) {
        res = max(res, distance(a[i], a[j]));
        if (crossOp(a[(i + 1) % n] - a[i], a[(j + 1) % n] - a[j]) < 0)
            i = (i + 1) % n;
        else
            j = (j + 1) % n;
    }
    return res;
}
// 分治法最近点对
db closestPair(Polygon s)
{
    sort(s.begin(), s.end());
    int n = s.size();
    if (n <= 1) return inf;
    int m = n / 2;
    db x = s[m].x;
    db res = min(closestPair(Polygon(s.begin(), s.begin() + m)),
        closestPair(Polygon(s.begin() + m, s.end())));
    sort(s.begin(), s.end());
    deque<int> deq;
    for (int i = 0; i < n; i++) {
        if (cmp(abs(s[i].x - x), res) >= 0) continue;
        while (!deq.empty() && cmp(s[deq.front()].y, s[i].y - res) <= 0)
            deq.pop_front();
        for (auto e : deq) res = min(res, distance(s[i], s[e]));
        deq.push_back(i);
    }
    return res;
}
struct Circle {
    Point o;
    db r;
    Circle() {}
    Circle(Point o_, db r_) { o = o_, r = r_; }
    friend istream& operator>>(istream& is, Circle& c)
    {
        return is >> c.o >> c.r;
    }
};
// 4 相离 3 外切 2 相交 1 内切 0 包含
int crossCC(Circle c1, Circle c2)
{
    if (c1.r < c2.r) swap(c1, c2);
    db d = len(c1.o - c2.o);
    if (sgn(c1.r + c2.r - d) == -1) return 4;
    if (sgn(c1.r + c2.r - d) == 0) return 3;
    if (sgn(c1.r - c2.r - d) == -1) return 2;
    if (sgn(c1.r - c2.r - d) == 0) return 1;
    return 0;
}
int pointInCircle(const Point& p, const Circle& c)
{
    db d = distance(c.o, p);
    int cp = cmp(d, c.r);
    if (cp > 0) return OUT;
    if (cp < 0) return IN;
    return ON;
}
Circle incircle_triangle(Point a, Point b, Point c)
{
    db A = len(b - c), B = len(c - a), C = len(a - b);
    Point o = a * A + b * B + c * C;
    o /= A + B + C;
    db r = len(cross(o - a, b - a) / len(b - a));
    return { o, r };
}
Circle circumcircle_triangle(Point a, Point b, Point c)
{
    db A = square(b - c);
    db B = square(c - a);
    db C = square(a - b);
    db s = A * (B + C - A), t = B * (C + A - B), u = C * (A + B - C);
    db l = s + t + u;
    s /= l, t /= l, u /= l;
    Point o = a * s + b * t + c * u;
    db r = len(a - o);
    return { o, r };
}
bool intersect(const Circle& c, const Line& l)
{
    return cmp(c.r, distancePL(c.o, l)) >= 0;
}
//  0 圆的外部，内部包括圆上包含线段 1 严格穿过圆
//  2圆心在s的投影点在线段s上（不包括端点）
int intersect(const Circle& c, const Segment& s)
{
    Point h = projection(c.o, s);
    if (cmp(distance(c.o, h), c.r) > 0) return 0;
    db d1 = len(c.o - s.a), d2 = len(c.o - s.b);
    if (cmp(c.r, d1) >= 0 && cmp(c.r, d2) >= 0) return 0;
    if (cmp(c.r, d1) * cmp(c.r, d2) < 0) return 1;
    if (sgn(dot(s.a - h, s.b - h)) < 0) return 2;
    return 0;
}

// l1 l2 的对称轴
vector<Line> corner(Line l1, Line l2)
{
    vector<Line> res;
    if (parallel(l1, l2)) {
        db d = distancePL(l2.a, l1) / 2.0;
        Point v1 = l1.b - l1.a;
        v1 = unit(v1) * d;
        Point p = l2.a + rotleft(v1);
        db d1 = distancePL(p, l1);
        db d2 = distancePL(p, l2);
        if (abs(d1 - d2) > d) {
            p = l2.a + rotright(v1);
        }
        res.push_back(Line(p, p + v1));
    }
    else {
        Point p = crosspointLL(l1, l2);
        Point v1 = l1.b - l1.a, v2 = l2.b - l2.a;
        v1 = unit(v1);
        v2 = unit(v2);
        res.push_back(Line(p, p + (v1 + v2)));
        res.push_back(Line(p, p + rotleft(v1 + v2)));
    }
    return res;
}
vector<Point> crosspointCL(Circle c, Line l)
{
    Point h = projection(c.o, l);
    db d = c.r * c.r - square(c.o - h);
    if (sgn(d) == -1) return {};
    if (sgn(d) == 0) return { h };
    Point x = unit(l.a - l.b) * sqrt(d);
    return { h - x, h + x };
}
Polygon crosspointCS(const Circle& c, const Segment& s)
{
    int num = intersect(c, s);
    if (num == 0) return {};
    auto res = crosspointCL(c, Line(s.a, s.b));
    if (num == 2) return res;
    if (sgn(dot(s.a - res[0], s.b - res[0])) > 0) swap(res[0], res[1]);
    return { res[0] };
}
Polygon crosspointCC(Circle c1, Circle c2)
{
    db r1 = c1.r, r2 = c2.r;
    if (r1 < r2) return crosspointCC(c2, c1);
    db d = len(c2.o - c1.o);
    int op = crossCC(c1, c2);
    if (op == 4 || op == 0) return {};
    Point v = c2.o - c1.o;
    if (op == 3 || op == 1) return { c1.o + unit(v) * r1 };
    db p = ((r1 * r1 - r2 * r2) / d + d) / 2, q = sqrt(r1 * r1 - p * p);
    Point h = c1.o + unit(v) * p;
    Point i = unit(rotleft(v));
    return { h + i * q, h - i * q };
}
// p1,p2 的角平分线 在p1p2逆时针方向
Line bisector(Point p1, Point p2)
{
    Circle c1 = Circle(p1, len(p1 - p2)), c2 = Circle(p2, len(p1 - p2));
    auto p = crosspointCC(c1, c2);
    if (cross(p2 - p1, p[0] - p1) > 0) swap(p[0], p[1]);
    return Line(p[0], p[1]);
}
// 点到圆的切点
Polygon tangent_to_circle(const Circle& c, const Point& p)
{
    return crosspointCC(c, Circle(p, sqrt(square(c.o - p) - c.r * c.r)));
}
// 两圆公切线
vector<Line> common_tangent(const Circle& c1, const Circle& c2)
{
    if (c1.r < c2.r) return common_tangent(c2, c1);
    vector<Line> res;
    db g = distance(c1.o, c2.o);
    if (sgn(g) == 0) return res;
    Point u = (c2.o - c1.o) / g, v = rotleft(u);
    // -1 外公切线 1 内公切线
    for (int s : {-1, 1}) {
        db h = (c1.r + c2.r * s) / g;
        if (cmp(1, h * h) == 0)
            res.emplace_back(c1.o + u * c1.r, c1.o + (u + v) * c1.r);
        else if (cmp(1, h * h) > 0) {
            Point U = u * h, V = v * sqrt(1 - h * h);
            res.emplace_back(c1.o + (U + V) * c1.r, c2.o - (U + V) * c2.r * s);
            res.emplace_back(c1.o + (U - V) * c1.r, c2.o - (U - V) * c2.r * s);
        }
    }
    return res;
}
// 三角剖分 一个端点在圆心的三角形和圆的2倍面积并
db commonarea_impl(const Circle& c, const Point& a, const Point& b)
{
    auto va = c.o - a, vb = c.o - b;
    db f = cross(va, vb), res = 0;
    if (sgn(f) == 0) return res;
    if (cmp(max(len(va), len(vb)), c.r) <= 0) return f;
    if (cmp(distancePS(c.o, Segment(a, b)), c.r) >= 0)
        return c.r * c.r * arg(Point(dot(va, vb), cross(va, vb)));
    auto cand = crosspointCS(c, Segment(a, b));
    if (cand.empty()) return res;
    if (cand.size() > 1u && dot(cand[1] - cand[0], a - cand[0]) > 0)
        swap(cand[0], cand[1]);
    cand.emplace(cand.begin(), a);
    cand.emplace_back(b);
    for (int i = 0; i + 1 < cand.size(); i++)
        res += commonarea_impl(c, cand[i], cand[i + 1]);
    return res;
}
db commonarea(const Circle& c, const Polygon& P)
{
    if (P.size() < 3) return 0;
    db res = 0;
    int n = P.size();
    for (int i = 0; i < n; i++) res += commonarea_impl(c, P[i], P[(i + 1) % n]);
    return res / 2;
}
db commonarea(Circle c1, Circle c2)
{
    db r1 = c1.r, r2 = c2.r;
    db d = len(c1.o - c2.o);
    if (cmp(r1 + r2, d) <= 0) return 0;
    if (cmp(fabs(r1 - r2), d) >= 0) return pi * min(r1, r2) * min(r1, r2);
    db res = 0;
    for (int _ = 0; _ < 2; _++) {
        r1 = c1.r, r2 = c2.r;
        db cosine = (d * d + r1 * r1 - r2 * r2) / (2 * d * r1);
        db theta = acos(cosine) * 2;
        res += (theta - sin(theta)) * r1 * r1 / 2;
        swap(c1, c2);
    }
    return res;
}
// 已知两点半径，求圆心位置
vector<Point> center_given_radius(const Point& a, const Point& b, const db& r)
{
    Point m = (b - a) * 0.5;
    db d1 = len(m);
    if (sgn(d1) == 0 || d1 > r) return {};
    db d2 = sqrt(r * r - d1 * d1);
    Point n = rotleft(m) * d2 / d1;
    Point p = a + m - n, q = a + m + n;
    if (p == q) return { p };
    return { p, q };
}

void solve()
{
    int n;
    cin >> n;
    Polygon P(n);
    for (int i = 0; i < n; i++)cin >> P[i];
    cout << fixed << setprecision(10) << closestPair(P) << "\n";
}
int main()
{
#ifdef LOCAL
#ifdef OPENSTACK
    int size = 128 << 20; // 64MB
    char* p = (char*) malloc(size) + size;
#if (defined _WIN64) or (defined __unix)
    __asm__("movq %0, %%rsp\n" ::"r"(p));
#else
    __asm__("movl %0, %%esp\n" ::"r"(p));
#endif
#endif
#endif
    IOS;
    int _ = 1;
    while (_--) {
        solve();
    }
#ifdef LOCAL
#ifdef OPENSTACK
    exit(0);
#else
    return 0;
#endif
#endif
}