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 <cmath>
#include <algorithm>
#include <cassert>
#include <limits>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
namespace lc {
static const double EPS = 1e-9;
inline double abs(double x){ return std::abs(x); }
inline bool tolerant_eq(double a, double b){ return abs(a - b) < EPS; }
}
namespace lc {
struct Point {
	double x;
	double y;
	explicit Point(const double &x = 0.0, const double &y = 0.0) :
		x(x), y(y)
	{ }
	Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
	Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
	Point operator*(double s) const { return Point(x * s, y * s); }
	Point operator*(const Point &p) const {
		return Point(x * p.x - y * p.y, x * p.y + y * p.x);
	}
	Point operator/(double s) const { return Point(x / s, y / s); }
	double abs() const { return sqrt(x * x + y * y); }
	double norm() const { return x * x + y * y; }
	Point unit() const { return *this / abs(); }
};
inline Point operator*(double s, const Point &p){ return p * s; }
inline bool tolerant_eq(const Point &a, const Point &b){
	return tolerant_eq(a.x, b.x) && tolerant_eq(a.y, b.y);
}
inline double cross(const Point &a, const Point &b){
	return a.x * b.y - a.y * b.x;
}
inline double dot(const Point &a, const Point &b){
	return a.x * b.x + a.y * b.y;
}
}
namespace lc {
struct Line {
	Point a;
	Point b;
	explicit Line(const Point &a = Point(), const Point &b = Point()) :
		a(a), b(b)
	{ }
	Point projection(const Point &p) const {
		double t = dot(p - a, b - a) / (b - a).norm();
		return a + t * (b - a);
	}
	Point direction() const {
		return (b - a).unit();
	}
};
}
namespace lc {
struct Segment {
	Point a;
	Point b;
	explicit Segment(const Point &a = Point(), const Point &b = Point()) :
		a(a), b(b)
	{ }
	Line to_line() const { return Line(a, b); }
};
}
namespace lc {
struct Circle {
	Point c;
	double r;
	explicit Circle(const Point &c = Point(), double r = 0.0) :
		c(c), r(r)
	{ }
};
inline bool tolerant_eq(const Circle &a, const Circle &b){
	return tolerant_eq(a.c, b.c) && tolerant_eq(a.r, b.r);
}
}
namespace lc {
inline bool intersect(const Point &a, const Segment &b){
	return (b.a - a).abs() + (b.b - a).abs() - (b.b - b.a).abs() < EPS;
}
inline bool intersect(const Segment &a, const Point &b){
	return intersect(b, a);
}
inline bool intersect(const Circle &a, const Circle &b){
	const double d = (a.c - b.c).abs();
	return d <= a.r + b.r && a.r + d >= b.r && b.r + d >= a.r;
}
}
namespace lc {
inline std::vector<Point> crossing_points(const Line &l, const Circle &c){
	const Point &p = l.projection(c.c);
	const double t = (p - c.c).abs();
	if(t > c.r + EPS){ return std::vector<Point>(); }
	if(t > c.r - EPS){ return std::vector<Point>(1, p); }
	const Point v = l.direction();
	const double d = sqrt(c.r * c.r - t * t);
	return std::vector<Point>({ p + d * v, p - d * v });
}
inline std::vector<Point> crossing_points(const Segment &s, const Circle &c){
	const std::vector<Point> cps(crossing_points(s.to_line(), c));
	std::vector<Point> result;
	for(const auto &p : cps){
		if(intersect(s, p)){ result.push_back(p); }
	}
	return result;
}
inline std::vector<Point> crossing_points(const Circle &a, const Circle &b){
	std::vector<Point> ret;
	if(!intersect(a, b)){ return ret; }
	if(tolerant_eq(a, b)){
		ret.push_back(a.c + Point(a.r, 0.0));
		ret.push_back(a.c + Point(-a.r, 0.0));
		ret.push_back(a.c + Point(0.0, a.r));
	}else{
		const double d = (a.c - b.c).abs();
		const double rc = (d * d + a.r * a.r - b.r * b.r) / (2.0 * d);
		const double rs = sqrt(a.r * a.r - rc * rc);
		const Point diff = (b.c - a.c) / d;
		const Point x = a.c + diff * Point(rc, rs);
		const Point y = a.c + diff * Point(rc, -rs);
		ret.push_back(x);
		if(!tolerant_eq(x, y)){ ret.push_back(y); }
	}
	return ret;
}
}
namespace lc {
class Polygon {
private:
	std::vector<Point> m_points;
public:
	explicit Polygon(size_t s, const Point &p = Point())
		: m_points(s, p)
	{ }
	Point &operator[](int i){ return m_points[i]; }
	Segment side(int i) const {
		return Segment(m_points[i], m_points[(i + 1) % m_points.size()]);
	}
	int size() const { return static_cast<int>(m_points.size()); }
	int contains(const Point &p) const {
		int result = -1;
		for(int i = 0; i < size(); ++i){
			Point a = m_points[i] - p;
			Point b = m_points[(i + 1) % size()] - p;
			if(a.y > b.y){ std::swap(a, b); }
			if(a.y <= 0.0 && b.y > 0.0 && cross(a, b) < 0.0){
				result = -result;
			}
			if(cross(a, b) == 0.0 && dot(a, b) <= 0.0){ return 0; }
		}
		return result;
	}
};
}
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cout << setiosflags(ios::fixed) << setprecision(10);
	int n, m;
	cin >> n;
	lc::Polygon poly(n);
	for(int i = 0; i < n; ++i){
		cin >> poly[i].x >> poly[i].y;
	}
	cin >> m;
	vector<lc::Point> centers(m);
	for(int i = 0; i < m; ++i){
		cin >> centers[i].x >> centers[i].y;
	}
	double lo = 0, hi = 1e8;
	for(int iter = 0; iter < 100; ++iter){
		const double r = (lo + hi) / 2;
		vector<lc::Circle> circles(m);
		for(int i = 0; i < m; ++i){
			circles[i] = lc::Circle(centers[i], r);
		}
		vector<lc::Point> testers;
		for(int i = 0; i < n; ++i){ testers.push_back(poly[i]); }
		for(int i = 0; i < m; ++i){
			for(int j = 0; j < m; ++j){
				const auto cps = lc::crossing_points(circles[i], circles[j]);
				for(const auto& p : cps){
					if(poly.contains(p) >= 0){ testers.push_back(p); }
				}
			}
			for(int j = 0; j < n; ++j){
				const auto cps = lc::crossing_points(poly.side(j), circles[i]);
				for(const auto& p : cps){ testers.push_back(p); }
			}
		}
		bool accept = true;
		for(const auto& p : testers){
			bool ok = false;
			for(const auto& c : circles){
				if((c.c - p).norm() < (r - lc::EPS) * (r - lc::EPS)){
					ok = true;
					break;
				}
			}
			if(!ok){
				accept = false;
				break;
			}
		}
		if(accept){
			hi = r;
		}else{
			lo = r;
		}
	}
	cout << lo << endl;
	return 0;
}