struct pt
{
    ld x, y;

    pt() {}
    pt(ll _x, ll _y) : x(_x), y(_y) {}
    pt(ld _x, ld _y) : x(_x), y(_y) {}

    pt operator-(pt p)
    {
        return {x - p.x, y - p.y};
    }
    pt operator+(pt p)
    {
        return {x + p.x, y + p.y};
    }
    pt operator*(ll k)
    {
        return {x * k, y * k};
    }
    pt operator*(ld k)
    {
        return {x * k, y * k};
    }

    pt operator/(ld k)
    {
        return {x / k, y / k};
    }

    ld angleWith(pt p)
    {
        return getAngle({x, y}, p);
    };

    static ld getAngle(pt a, pt b)
    {
        return atan2(a ^ b, a * b);
    }

    ld operator*(pt p)
    {
        return x * p.x + y * p.y;
    }
    ld operator^(pt p)
    {
        return -y * p.x + x * p.y;
    }

    ld sqlen()
    {
        return x * x + y * y;
    }

    ld len()
    {
        return hypot(abs(x), abs(y));
    }

    pt perp()
    {
        return {y, -x};
    }

    bool operator==(pt p) { return abs(x - p.x) < eps && abs(y - p.y) < eps; }
    bool operator!=(pt p) { return !(p == pt{x, y}); }
};

ll sign(ld val)
{
    if (abs(val) < eps)
        return 0;
    if (val >= eps)
        return 1;
    return -1;
}

bool belongAngle(pt P, pt A, pt O, pt B)
{
    pt OA = A - O, OP = P - O, OB = B - O;

    return sign(OP ^ OA) == 0 && sign(OP * OA) >= 0 ||
           sign(OP ^ OB) == 0 && sign(OP * OB) >= 0 ||
           sign(OA ^ OP) == sign(OP ^ OB) && sign(OP ^ OB) == sign(OA ^ OB);
}

bool belongPolygon(pt p, vc<pt> &polygon)
{

    if (!belongAngle(p, polygon.back(), polygon[0], polygon[1]))
        return false;

    ll l = 1, r = polygon.size() - 1;

    while (l + 1 != r)
    {
        ll m = (l + r) / 2;

        if (belongAngle(p, polygon[l], polygon[0], polygon[m]))
            r = m;
        else
            l = m;
    }

    return belongAngle(p, polygon[l], polygon[0], polygon[r]) && belongAngle(p, polygon[0], polygon[l], polygon[r]);
}

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

struct line
{

    pt v;
    ld c;

    line() {}
    line(pt p, pt q) : v(q - p), c(v ^ p) {}
    line(ld A, ld B, ld C) : v(B, -A), c(C) {}

    ld side(pt p)
    {
        return (v ^ p) - c;
    }

    ld dist(pt p)
    {
        return side(p) / v.len();
    }

    pt projection(pt p)
    {
        return p - v.perp() * side(p) / (v ^ v.perp());
    }
    pt reflection(pt p)
    {
        return p - v.perp() * (2 * side(p) / (v ^ v.perp()));
    }
};

line getBisector(pt A, pt O, pt B)
{
    line OA(O, A), OB(O, B);

    pt vOA = OA.v, vOB = OB.v;

    vOA = vOA * abs(100 / vOA.len());
    vOB = vOB * abs(100 / vOB.len());

    pt vOM = vOA + vOB;

    line OM(O, O + vOM);
    return OM;
}

bool intersection(line l1, line l2, pt &out)
{
    ld d = l1.v ^ l2.v;
    if (d == 0)
        return false;

    out = (l2.v * l1.c - l1.v * l2.c) / d;
    return true;
}
ld lineRayDist(pt A, pt B, pt C, pt D)
{

    line l(A, B), ray(C, D);

    if (sign(l.v ^ ray.v) == 0)
        return abs(l.dist(C));
    else if (sign(l.side(C)) == 0)
        return 0;
    else
    {
        pt M;
        intersection(l, ray, M);

        pt CM = M - C, CD = D - C;
        if (sign(CM * CD) >= 0)
            return 0;
        else
            return abs(l.dist(C));
    }
}

ld pntSegDist(pt A, pt C, pt D)
{
    pt CD = D - C, CA = A - C, DC = C - D, DA = A - D;
    if (CD * CA >= 0 && DC * DA >= 0)
        return abs(line(C, D).dist(A));
    else
        return min(CA.len(), DA.len());
}

ld segSegDist(pt A, pt B, pt C, pt D)
{
    pt AB = B - A, AC = C - A, BA = A - B, BC = C - B, AD = D - A, BD = D - B, CD = D - C, DC = C - D, CA = A - C, DA = A - D, CB = B - C, DB = B - D;
    if (
        A == C || A == D || B == C || B == D ||

        sign(AB ^ AC) == 0 && sign(AB * AC) >= 0 && sign(BA * BC) >= 0 ||
        sign(AB ^ AD) == 0 && sign(AB * AD) >= 0 && sign(BA * BD) >= 0 ||
        sign(CD ^ CA) == 0 && sign(CD * CA) >= 0 && sign(DC * DA) >= 0 ||
        sign(CD ^ CB) == 0 && sign(CD * CB) >= 0 && sign(DC * DB) >= 0 ||

        sign(CD ^ CA) != sign(CD ^ CB) && sign(AB ^ AD) != sign(AB ^ AC))
        return 0;
    else
        return min({pntSegDist(A, C, D), pntSegDist(B, C, D), pntSegDist(C, A, B), pntSegDist(D, A, B)});
}

ld raySegDist(pt C, pt D, pt A, pt B)
{
    line l(C, D);
    pt AB = B - A, BA = A - B, CD = D - C, AC = C - A, BC = C - B, CA = A - C, CB = B - C;

    // параллельны
    if (sign(AB ^ CD) == 0)
    {
        // на одной прямой
        if (sign(AB ^ AC) == 0)
        {
            if (A == C || B == C || sign(CA * CD) >= 0 || sign(CB * CD) >= 0)
                return 0;
            else
                return min(AC.len(), BC.len());
        }

        // не на одной прямой
        else
        {
            if (sign(CA * CD) >= 0 || sign(CB * CD) >= 0)
                return abs(l.dist(A));
            else
                return min(AC.len(), BC.len());
        }
    }
    else
    {
        line l2(A, B);
        pt M;
        intersection(l, l2, M);

        pt AM = M - A, MA = A - M, BM = M - B, MB = B - M, CM = M - C, MC = C - M;
        if (A == C || B == C ||
            sign(CA ^ CD) == 0 && sign(CA * CD) >= 0 ||
            sign(CB ^ CD) == 0 && sign(CB * CD) >= 0 ||
            sign(AC ^ AB) == 0 && sign(AC * AB) >= 0 && sign(BC * BA) >= 0 ||
            sign(AM ^ AB) == 0 && sign(AM * AB) >= 0 && sign(BM * BA) >= 0 && sign(CM ^ CD) == 0 && sign(CM * CD) >= 0)
            return 0;

        ld ans = min(AC.len(), BC.len());

        remin(ans, pntSegDist(C, A, B));

        if (A == C || sign(CA * CD) >= 0)
            remin(ans, abs(l.dist(A)));

        if (B == C || sign(CB * CD) >= 0)
            remin(ans, abs(l.dist(B)));
        return ans;
    }
}

ld rayRayDist(pt A, pt B, pt C, pt D)
{
    line l1(A, B), l2(C, D);
    pt AB = B - A, CD = D - C, AC = C - A, CA = A - C;

    // параллельны
    if (sign(AB ^ CD) == 0)
    {

        // на одной прямой
        if (sign(AB ^ AC) == 0)
        {
            if (A == C || sign(AB * AC) >= 0 || sign(AB * CD) >= 0)
                return 0;
            return AC.len();
        }

        // не на одной прямой
        else
        {
            if (sign(AC * AB) >= 0 || sign(AB * CD) > 0)
                return abs(l1.dist(C));
            else
                return AC.len();
        }
    }

    // непараллельны
    else
    {
        pt M;
        intersection(l1, l2, M);

        pt CM = M - C, AM = M - A;

        if (A == C ||
            sign(AC ^ AB) == 0 && sign(AC * AB) >= 0 ||
            sign(CA ^ CD) == 0 && sign(CA * CD) >= 0 ||
            sign(CM * CD) >= 0 && sign(AM * AB) >= 0)
            return 0;

        ld ans = AC.len();

        pt X = l1.projection(C), Y = l2.projection(A);
        pt AX = X - A, CY = Y - C;
        if (X == A || sign(AX * AB) >= 0)
            remin(ans, (C - X).len());

        if (Y == C || sign(CY * CD) >= 0)
            remin(ans, (A - Y).len());

        return ans;
    }
}
