Chinol Choco

Time Limit : 2 sec, Memory Limit : 262144 KB

Problem K: Chinol Choco

Problem

チョコレート会社チノルチョコは新しい店をn店建てることにした。
それぞれの店は各店長に建てたい場所の候補を2つ用意してもらい、どちらかの場所に建てる。

チノルチョコではm種類のチョコレートを販売しており、それぞれ別の工場で製造している。
すべての店で全種類のチョコレートを販売する。
チノルチョコではチョコレートを搬送するためのトラックを1台しか所有しておらず、1台のトラックでは1店分のチョコレートしか運べない。
そのため、トラックは店から別の店へ移動する際にすべての工場を回る必要がある。

ある店から別の店へ移動する時の最短移動距離の最大が最小になるように店を配置した時の、最大の移動距離を求めよ。

同じ場所に複数の店や工場が存在することができる。

Input

入力は以下の形式で与えられる。

n m
a0 b0 c0 d0
...
an−1 bn−1 cn−1 dn−1
x0 y0
...
xm−1 ym−1

入力はすべて整数で与えられる。
1行目にチノルチョコの店の数n、チョコレートを製造している工場の数mが空白区切りで与えられる。
2行目からn行にそれぞれの店を建てる場所の候補の座標(ai,bi),(ci,di)が空白区切りで与えられる。
2+n行目からm行に工場の座標(xi,yi)が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  • 2 ≤ n ≤ 200
  • 1 ≤ m ≤ 15
  • 0 ≤ ai,bi,ci,di,xi,yi ≤ 1000

Output

最短移動距離の最大が最小になるように店を配置した時の、最大の移動距離を出力せよ。
誤差が10−6を超えてはならない。

Sample Input 1

2 1
0 0 5 5
3 3 6 6
2 2

Sample Output 1

4.2426406871

Sample Input 2

2 2
0 0 6 0
7 0 3 0
4 0
5 0

Sample Output 2

3.0000000000

Source: Aizu Competitive Programming Camp 2017 , Day 2, Aizu-Wakamatsu, Japan, 2017-09-19