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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

typedef long double P_type;
typedef complex<P_type> P;
const P_type P_eps = 1e-9; //整数の時はゼロ

namespace std{
  template<class T> bool operator<(const complex<T> &a, const complex<T> &b){
    return a.real() == b.real() ? a.imag() < b.imag() : a.real() < b.real();
  }
};

P rotate(P p, double theta){
  return p * P(cos(theta), sin(theta));
}

//内積
P_type dot(P a, P b) {
  return (a * conj(b)).real();
}

//外積
P_type cross(P a, P b) {
  return (conj(a) * b).imag();
}

//反時計回り
int ccw(P a, P b, P c){
  if(cross(b-a,c-a) > P_eps) return 1; //COUNTER_CLOCKWISE
  if(cross(b-a,c-a) < -P_eps) return -1; //CLOCKWISE
  if(dot(b-a,c-a) < -P_eps) return -2; //c -> a -> b
  if(dot(a-b,c-b) < -P_eps) return 2; //a -> b -> c
  return 0; //a -> c -> b
}

/* 線分abと点cの距離 */
P_type distanceSP(P a, P b, P c) {
  if ( dot(b-a, c-a) < P_eps ) return abs(c-a);
  if ( dot(a-b, c-b) < P_eps ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* 直線abと点cの距離 */
P_type distanceLP(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* 円の点包含判定 */
bool isContainedCP(P c, double r, P p){
  return abs(c-p) < r - P_eps; //円周上を含まない
  //return abs(c-p) < r + P_eps; //円周上を含む
}

/* 直線交差判定 */
bool isIntersectedLL(P a1, P a2, P b1, P b2){
  return abs(cross(a1-a2, b1-b2)) > P_eps;
}

/* 線分交差判定 */
bool isIntersectedSS(P a1, P a2, P b1, P b2){
  
  //線分a と 直線b
  int a = ccw(b1,b2,a1);
  int b = ccw(b1,b2,a2);
  
  //線分b と 直線a
  int c = ccw(a1,a2,b1);
  int d = ccw(a1,a2,b2);
  
  return a*b < P_eps && c*d < P_eps; // T字を除く時は -P_eps
}

/* 直線線分交差判定 */
bool isIntersectedLS(P a1, P a2, P b1, P b2){  
  int a = ccw(a1,a2,b1);
  int b = ccw(a1,a2,b2);
  
  // 直線上のとき a or b = 0 or -2 or 2
  return (a%2)*(b%2) <= 0; // T字を除く時は (** < 0)
}

/* 円交差判定 */
bool isIntersectedCC(P c1, double r1, P c2, double r2){
  double dist = abs(c1 - c2);
  
  return abs(r1 - r2) < dist + P_eps && dist - P_eps < r1 + r2; //外接内接を含む
  //return abs(r1 - r2) < dist - P_eps && dist + P_eps < r1 + r2; //外接内接を除く
}

/* 円直線交差判定 */
bool isIntersectedCL(P c, double r, P a1, P a2){
  return distanceLP(a1, a2, c) < r + P_eps; //接する場合を含まない場合 - P_eps
}

/* 円線分交差判定 */
bool isIntersectedCS(P c, double r, P a1, P a2){
  return isContainedCP(c,r,a1) &&
    isContainedCP(c,r,a2) &&
    distanceLP(a1, a2, c) < r + P_eps; //接する場合を含まない場合 - P_eps
}

/* 直線/線分交点 */
P getCrosspointLL(P a1, P a2, P b1, P b2) {
  //assert(isIntersectedLL(a1, a2, b1, b2));
  P a = a2 - a1;
  P b = b2 - b1;
  return a1 + a * cross(b, b1-a1) / cross(b, a);
}

P getCrosspointSS(P a1, P a2, P b1, P b2){
  //assert(isIntersectedSS(a1, a2, b1, b2));
  return getCrosspointLL(a1, a2, b1, b2);
}

/* 円交点 */
pair<P,P> getCrosspointCC(P c1, P_type r1, P c2, P_type r2){
  //assert(isIntersectedCC(c1, r1, c2, r2));
  
  double dist = abs(c1 - c2);
  double a = acos((r1*r1 + dist*dist - r2*r2) / (2 * r1 * dist));
  return {c1 + polar(r1, arg(c2 - c1) + a), c1 + polar(r1, arg(c2 - c1) - a)};
}

/* 円線分交点 */
pair<P,P> getCrosspointCS(P c, double r, P a1, P a2){
  //assert(isIntersectedCS(c1, r1, c2, r2));
  
  P base1 = a2 - a1;
  P proj = a1 + base1 * dot(c - a1, base1) / norm(base1); //射影
  P e = (a2 - a1) / abs(a2 - a1);
  P base2 = sqrt(r*r - norm(proj - c));
  return {proj + e*base2, proj - e*base2};
}

/* 多角形-点包含 */
bool iscontainedPolyP(vector<P> &g, P p){
  int n = g.size();
  bool f = false;
  for(int i=0;i<n;i++){
    P a = g[i] - p, b = g[(i+1)%n] - p;
    if(abs(cross(a,b)) < P_eps && dot(a,b) < P_eps) return true; //辺上
    if(a.imag() > b.imag()) swap(a,b);
    if(a.imag() < P_eps && P_eps < b.imag() && cross(a,b) > P_eps) f = !f;
  }
  return f; //内部 or 外部
}

/* 射影(直線abとpからの垂線との交点) */
P getProject(P a, P b, P p){
  P base = b - a;
  return a + base * dot(p - a, base) / norm(base);
}

/* 反射(直線abを対称軸としたpの線対称の位置) */
P getReflection(P a, P b, P p){
  return p + (getProject(a, b, p) - p) * (P_type)2.0;
}


int main(){
  int n, m, x, y;
  P pxy[101], cxy[101];
  vector<P> pol;

  scanf("%d", &n);
  
  for(int i=0;i<n;i++){
    scanf("%d%d", &x, &y);
    pxy[i] = P(x, y);
    pol.push_back(pxy[i]);
  }
  pxy[n] = pxy[0];
  

  scanf("%d", &m);
  
  for(int i=0;i<m;i++){
    scanf("%d%d", &x, &y);
    cxy[i] = P(x, y);
  }

  P_type l = 0, r = 1e6;

  P_type epseps = 1e-7;
  
  while(abs(l-r) > 1e-6){
    P_type R = (l+r)/2;
    vector<P> vec; 
    
    for(int i=0;i<m;i++){
      for(int j=i+1;j<m;j++){
        if(!isIntersectedCC(cxy[i], R, cxy[j], R)) continue;
        auto gc = getCrosspointCC(cxy[i], R, cxy[j], R);

        auto e = (gc.first - gc.second) / abs(gc.first - gc.second) * epseps;

        vec.push_back(gc.first + e);
        //vec.push_back(gc.first + e * (P_type)-1);
        //vec.push_back(gc.second + e * (P_type)1);
        vec.push_back(gc.second + e * (P_type)-1);
      }
    }

    P_type mone = -1;

    for(int j=0;j<n;j++){

      for(int i=0;i<m;i++){
        auto gc = getCrosspointCS(cxy[i], R, pxy[j], pxy[j+1]);
        auto e = (gc.first - gc.second) / abs(gc.first - gc.second) * epseps;
        auto em = e*mone;
        vec.push_back(gc.first + e);
        //vec.push_back(gc.first + em);
        //vec.push_back(gc.second + e);
        vec.push_back(gc.second + em);
      }
    }

    bool res = true;
    
    for(int i=0;i<vec.size() && res;i++){
      if(iscontainedPolyP(pol, vec[i])){

        bool f = false;
        for(int j=0;j<m && !f;j++){
          f |= isContainedCP(cxy[j], R, vec[i]);
        }

        res &= f;
      }
    }

    if(res){
      r = R;
    }else{
      l = R;
    }
  }

  printf("%.10lf\n", (double)l);
  
  
  return 0;
}