Problem: Problem

Given a convex polygon consisting of $ N $ vertices and the center coordinates of $ M $ circles. The radius of all circles is $ r $.

I want to find the minimum real number $ r $ that satisfies the following conditions.

Condition: Every point inside a convex polygon is contained in at least one circle.

Constraints

The input satisfies the following conditions.

* $ 3 \ le N \ le 100 $
* $ 1 \ le M \ le 100 $
* $ -10 ^ 5 \ le px_i, py_i \ le 10 ^ 5 $
* $ -10 ^ 5 \ le cx_i, cy_i \ le 10 ^ 5 $
* No matter which of the three vertices of the convex polygon is selected, they do not exist on the same straight line.

Input

All inputs are given as integers in the following format:


$ N $
$ px_1 $ $ py_1 $
$ px_2 $ $ py_2 $
::
$ px_N $ $ py_N $
$ M $
$ Cx_1 $ $ cy_1 $
$ cx_2 $ $ cy_2 $
::
$ Cx_M $ $ cy_M $


The $ 1 $ line is given an integer $ N $ that represents the number of vertices of the convex polygon.
Information on each vertex of the convex polygon is given in the counterclockwise order from the $ 2 $ line to the $ 2 + N-1 $ line. The $ 1 + i $ line is given $ px_i $ $ py_i $, which represents the coordinates of the $ i $ th vertex, separated by blanks.
The $ 2 + N $ line is given the integer $ M $, which represents the number of circles.
Information on the center coordinates of the circle is given from the $ 2 + N + 1 $ line to the $ 2 + N + M $ line. On the $ 2 + N + i $ line, $ cx_i $ $ cy_i $ representing the center coordinates of the $ i $ th circle is given, separated by blanks.

Output

Outputs the radius $ r $ of the smallest circle that satisfies the condition.
However, absolute or relative errors up to $ 10 ^ {-5} $ are acceptable.

Examples

Input

4
2 3
1 2
2 1
3 2
4
1 3
1 1
3 3
3 1


Output

1.414213562373


Input

7
-96469 25422
-55204 -45592
-29140 -72981
98837 -86795
92303 63297
19059 96012
-67980 70342
17
-4265 -14331
33561 72343
52055 98952
-71189 60872
10459 -7512
-11981 57756
-78228 -28044
37397 -69980
-27527 -51966
22661 -16694
13759 -59976
86539 -47703
17098 31709
-62497 -70998
-57608 59799
-1904 -35574
-73860 121


Output

75307.220122044484

Solution (in CPP):

Solution:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }



////////////////////////////
// 基本要素 (点, 線分, 円)
////////////////////////////

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acos(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};

/* Circle */
struct Circle : Point {
    DD r;
    Circle(Point p = Point(0.0, 0.0), DD r = 0.0) : Point(p), r(r) {}
    friend ostream& operator << (ostream &s, const Circle &c) {return s << '(' << c.x << ", " << c.y << ", " << c.r << ')';}
};


int ccw(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < 0) return 2;
    if (norm(b-a) < norm(c-a)) return -2;
    return 0;
}

Point proj(Point p, Line l) {
    DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}
Point refl(Point p, Line l) {
    return p + (proj(p, l) - p) * 2;
}
bool isinterPL(Point p, Line l) {
    return (abs(p - proj(p, l)) < EPS);
}
bool isinterPS(Point p, Line s) {
    return (ccw(s[0], s[1], p) == 0);
}
bool isinterLL(Line l, Line m) {
    return (abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
            abs(cross(l[1] - l[0], m[0] - l[0])) < EPS);
}
bool isinterSS(Line s, Line t) {
    if (eq(s[0], s[1])) return isinterPS(s[0], t);
    if (eq(t[0], t[1])) return isinterPS(t[0], s);
    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);
}
DD distancePL(Point p, Line l) {
    return abs(p - proj(p, l));
}
DD distancePS(Point p, Line s) {
    Point h = proj(p, s);
    if (isinterPS(h, s)) return abs(p - h);
    return min(abs(p - s[0]), abs(p - s[1]));
}
DD distanceLL(Line l, Line m) {
    if (isinterLL(l, m)) return 0;
    else return distancePL(m[0], l);
}
DD distanceSS(Line s, Line t) {
    if (isinterSS(s, t)) return 0;
    else return min(min(distancePS(s[0], t), distancePS(s[1], t)), min(distancePS(t[0], s), distancePS(t[1], s)));
}



vector<Point> crosspoint(Line l, Line m) {
    vector<Point> res;
    DD d = cross(m[1] - m[0], l[1] - l[0]);
    if (abs(d) < EPS) return vector<Point>();
    res.push_back(l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) / d);
    return res;
}
vector<Point> crosspoint(Circle e, Circle f) {
    vector<Point> res;
    DD d = abs(e - f);
    if (d < EPS) return vector<Point>();
    if (d > e.r + f.r + EPS) return vector<Point>();
    if (d < abs(e.r - f.r) - EPS) return vector<Point>();
    DD rcos = (d * d + e.r * e.r - f.r * f.r) / (2.0 * d), rsin;
    if (e.r - abs(rcos) < EPS) rsin = 0;
    else rsin = sqrt(e.r * e.r - rcos * rcos);
    Point dir = (f - e) / d;
    Point p1 = e + dir * Point(rcos, rsin);
    Point p2 = e + dir * Point(rcos, -rsin);
    res.push_back(p1);
    if (!eq(p1, p2)) res.push_back(p2);
    return res;
}
vector<Point> crosspoint(Circle e, Line l) {
    vector<Point> res;
    Point p = proj(e, l);
    DD rcos = abs(e - p), rsin;
    if (rcos > e.r + EPS) return vector<Point>();
    else if (e.r - rcos < EPS) rsin = 0;
    else rsin = sqrt(e.r * e.r - rcos * rcos);
    Point dir = (l[1] - l[0]) / abs(l[1] - l[0]);
    Point p1 = p + dir * rsin;
    Point p2 = p - dir * rsin;
    res.push_back(p1);
    if (!eq(p1, p2)) res.push_back(p2);
    return res;
}

vector<Point> crosspoint_LS(Line l, Line s) {
    vector<Point> res;
    DD d = cross(s[1] - s[0], l[1] - l[0]);
    if (abs(d) < EPS) return vector<Point>();
    Point p = l[0] + (l[1] - l[0]) * cross(s[1] - s[0], s[1] - l[0]) / d;
    if (isinterPS(p, s)) res.push_back(p);
    return res;
}
vector<Point> crossPoint_LPo(Line l, vector<Point> ps) {
    int n = ps.size();
    vector<Point> res;
    for (int i = 0; i < n; ++i) {
        int f = i, t = (i+1)%n;
        Line s(ps[f], ps[t]);
        vector<Point> temp = crosspoint_LS(l, s);
        for (int j = 0; j < temp.size(); ++j) {
            bool exist = false;
            for (int k = 0; k < res.size(); ++k) {
                if (eq(res[k], temp[j])) exist = true;
            }
            if (!exist) res.push_back(temp[j]);
        }
    }
    return res;
}


// convex cut
int ccw_for_convexcut(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < 0) return 2;
    if (norm(b-a) < norm(c-a)) return -2;
    return 0;
}
vector<Point> crosspoint_for_convexcut(const Line &l, const Line &m) {
    vector<Point> res;
    DD d = cross(m[1] - m[0], l[1] - l[0]);
    if (abs(d) < EPS) return vector<Point>();
    res.push_back(l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) / d);
    return res;
}
vector<Point> ConvexCut(const vector<Point> &pol, const Line &l) {
    vector<Point> res;
    for (int i = 0; i < pol.size(); ++i) {
        Point p = pol[i], q = pol[(i+1)%pol.size()];
        if (ccw_for_convexcut(l[0], l[1], p) != -1) {
            if (res.size() == 0) res.push_back(p);
            else if (!eq(p, res[res.size()-1])) res.push_back(p);
        }
        if (ccw_for_convexcut(l[0], l[1], p) * ccw_for_convexcut(l[0], l[1], q) < 0) {
            vector<Point> temp = crosspoint_for_convexcut(Line(p, q), l);
            if (temp.size() == 0) continue;
            else if (res.size() == 0) res.push_back(temp[0]);
            else if (!eq(temp[0], res[res.size()-1])) res.push_back(temp[0]);
        }
    }
    return res;
}

// Voronoi-diagram (今回は使わない)
Line bisector(const Point &p, const Point &q) {
    Point c = (p + q) / 2.0L;
    Point v = (q - p) * Point(0.0L, 1.0L);
    v = v / abs(v);
    return Line(c - v, c + v);
}
vector<Point> Voronoi(vector<Point> pol, const vector<Point> &ps, int ind) {
    for (int i = 0; i < ps.size(); ++i) {
        if (i == ind) continue;
        Line l = bisector(ps[ind], ps[i]);
        pol = ConvexCut(pol, l);
    }
    return pol;
}





int main() {
    int N, M;
    cin >> N;
    vector<Point> pol(N);
    for (int i = 0; i < N; ++i) cin >> pol[i].x >> pol[i].y;
    cin >> M;
    vector<Point> ps(M);
    for (int i = 0; i < M; ++i) cin >> ps[i].x >> ps[i].y;
    double res = 0.0;
    for (int i = 0; i < M; ++i) {
        vector<Point> npol = Voronoi(pol, ps, i);
        for (auto p : npol) {
            double tmp = 1LL<<60;
            for (int j = 0; j < M; ++j) tmp = min(tmp, abs(ps[j] - p));
            res = max(res, tmp);
        }
    }
    cout << fixed << setprecision(10) << res << endl;
}