E - Booster Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

2 次元平面上に N 個の街と M 個の宝箱があります。街 i は座標 (X_i,Y_i) に、宝箱 i は座標 (P_i,Q_i) にあります。

高橋君は原点を出発し、N 個の街全てを訪れたのち原点に戻る旅行をしようと考えています。
宝箱を訪れる必要はありませんが、宝箱の中にはそれぞれブースターが 1 つあり、ブースターを拾うごとに移動速度が 2 倍になります。

高橋君の最初の移動速度が単位時間あたり 1 であるとき、旅行にかかる時間の最小値を求めてください。

制約

  • 1 \leq N \leq 12
  • 0 \leq M \leq 5
  • -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
  • (0,0),(X_i,Y_i),(P_i,Q_i) は相異なる
  • 入力は全て整数

入力

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

N M
X_1 Y_1
\vdots
X_N Y_N
P_1 Q_1
\vdots
P_M Q_M

出力

答えを出力せよ。なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

2 1
1 1
0 1
1 0

出力例 1

2.5000000000

以下のように移動するのが最適解の一つです。

  • 原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
  • 宝箱 1 から街 1 までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
  • 街 1 から街 2までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる
  • 街 2から原点までの距離 1 を速さ 2 で移動する。時間が 0.5 かかる

入力例 2

2 1
1 1
0 1
100 0

出力例 2

3.4142135624

以下のように移動するのが最適解の一つです。

  • 原点 から街 1 までの距離 1.41\ldots を速さ 1 で移動する。時間が 1.41\ldots かかる
  • 街 1 から街 2 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
  • 街 2 から原点までの距離 1 を速さ 1 で移動する。時間が 1 かかる

入力例 3

1 2
4 4
1 0
0 1

出力例 3

4.3713203436

以下のように移動するのが最適解の一つです。

  • 原点から宝箱 1 までの距離 1 を速さ 1 で移動する。時間が 1 かかる
  • 宝箱 1 から宝箱 2 までの距離 1.41\ldots を速さ 2 で移動する。時間が 0.707\ldots かかる
  • 宝箱 2 から街 1 までの距離 5 を速さ 4 で移動する。時間が 1.25 かかる
  • 街 1 から原点までの距離 5.65\ldots を速さ 4 で移動する。時間が 1.41\ldots かかる

Score : 500 points

Problem Statement

In a two-dimensional plane, there are N towns and M chests. Town i is at the coordinates (X_i,Y_i), and chest i is at the coordinates (P_i,Q_i).

Takahashi will go on a trip where he starts at the origin, visits all N towns, and then returns to the origin.
It is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by 2.

Takahashi's initial moving speed is 1. Find the shortest time needed to complete the trip.

Constraints

  • 1 \leq N \leq 12
  • 0 \leq M \leq 5
  • -10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9
  • (0,0), (X_i,Y_i), and (P_i,Q_i) are distinct.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 Y_1
\vdots
X_N Y_N
P_1 Q_1
\vdots
P_M Q_M

Output

Print the answer. Your output will be considered correct if the absolute or relative error from the judge's answer is at most 10^{-6}.

Sample Input 1

2 1
1 1
0 1
1 0

Sample Output 1

2.5000000000

Here is one optimal way to complete the trip.

  • Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
  • Go the distance 1 from chest 1 to town 1 at a speed of 2, taking a time of 0.5.
  • Go the distance 1 from town 1 to town 2 at a speed of 2, taking a time of 0.5.
  • Go the distance 1 from town 2 to the origin at a speed of 2, taking a time of 0.5.

Sample Input 2

2 1
1 1
0 1
100 0

Sample Output 2

3.4142135624

Here is one optimal way to complete the trip.

  • Go the distance 1.41\ldots from the origin to town 1 at a speed of 1, taking a time of 1.41\ldots.
  • Go the distance 1 from town 1 to town 2 at a speed of 1, taking a time of 1.
  • Go the distance 1 from town 2 to the origin at a speed of 1, taking a time of 1.

Sample Input 3

1 2
4 4
1 0
0 1

Sample Output 3

4.3713203436

Here is one optimal way to complete the trip.

  • Go the distance 1 from the origin to chest 1 at a speed of 1, taking a time of 1.
  • Go the distance 1.41\ldots from chest 1 to chest 2 at a speed of 2, taking a time of 0.707\ldots.
  • Go the distance 5 from chest 2 to town 1 at a speed of 4, taking a time of 1.25.
  • Go the distance 5.65\ldots from town 1 to the origin at a speed of 4, taking a time of 1.41\ldots.