Roads on Towns

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem E: 街を駆ける道

ネーヴァ王国には、トタタ族とツテテ族、2種類の民族が暮らしている。トタタ族の最大の特徴は、 酢豚にパイナップルを入れて食べることである。だがツテテ族は、パイナップルに酢豚を入れて食べ る。こんな2つの民族がお互いに仲良くやっていけるはずもなく、トタタ族とツテテ族は、何百年も の昔からずっといがみ合いを続けてきた。

そんなある日、ネーヴァ王のもとに、2つの民族から嘆願書が届いた。それによるとトタタ族は、自 分たちが暮らす街Aと街Bのあいだを結ぶ道を建設してほしいらしい。一方でツテテ族も、自分たち が暮らす街Cと街Dのあいだを結ぶ道を建設してほしいらしい。

2つの民族が衝突するのを防ぐため、トタタ族が通る道とツテテ族が通る道を交差させることはでき ない。また、技術的な制約により、2つの街のあいだを一直線に結ぶような道しか建設することはで きない。つまり、必要ならば街Aと街Bを直接道で結ばずに、いくつかのトタタ族の街を経由して街 Aと街Bを間接的に結ぶことになるだろう(もちろん、ツテテ族の街を経由してはならない)。その 際、トタタ族の街を結ぶ道どうしは交差していてもよい。街Cと街Dについても同様である。

道を建設するには、その長さに比例したコストがかかる。なので、条件をみたしつつ、できるだけ建 設する道の長さの合計が短くなるようにしたい。さて、長さの最小値はいくつになるだろうか。

Input

NA NB
xA,1 yA,1
xA,2 yA,2
.
.
.
xA,NA yA,NA
xB,1 yB,1
xB,2 yB,2
.
.
.
xB,NB yB,NB

入力の1行目には、整数NA(2 ≤ NA ≤ 1,000)と整数NB(2 ≤ NB ≤ 1,000)が、空白区切りで書かれている。これは、ネーヴァ王国にはトタタ族が暮らす街がNA 個、ツテテ族が暮らす街がNB 個あることをあらわす。初期状態では、どこにも道は建設されていない。

続くNA 行には、整数xA,i(-10,000 ≤ xA,i ≤ 10,000)と整数yA,i(-10,000 ≤ yA,i ≤ 10,000)が、空白区切りで書かれている。ネーヴァ王国の地理は2次元直交座標平面であらわされ、1+ i 行目に書かれた整数xA,iyA,i は、トタタ族が暮らすi 番目の街の位置座標が(xA,i, yA,i) であることをあらわす。(xA,1, yA,1) と(xA,2, yA,2) が、結ぶべき2つの街の座標である。

続くNB 行には、整数xB,i(-10,000 ≤ xB,i ≤ 10,000)と整数yB,i(-10,000 ≤ yB,i ≤ 10,000)が、空白区切りで書かれている。1+ NA + i 行目に書かれた整数xB,iyB,i は、ツテテ族が暮らすi 番目の街の位置座標が(xB,i, yB,i) であることをあらわす。(xB,1, yB,1) と(xB,2, yB,2) が、結ぶべき2つの街の座標である。

どの2つの街の座標も異なっており、どの3つの街も同一直線上にないと仮定してよい。

Output

問題文の条件をみたすように道を建設したとき、道の長さの合計の最小値を出力せよ。ここで言う 「長さ」とは、ユークリッド距離のことである。ただし、どうやっても条件をみたす道を建設できな いときは、代わりに-1 を出力せよ。出力は誤差を含んでいてもよいが、真の値との相対誤差が10-9未満でなければならない。

Sample Input 1

2 2
0 0
1 1
2 0
2 -1

Sample Output 1

2.414213562373

Sample Input 2

2 3
4 0
0 0
2 3
2 -2
3 1

Sample Output 2

-1

Sample Input 3

5 2
-2 1
1 2
-1 3
-1 5
1 4
0 4
0 0

Sample Output 3

12.359173603117

Source: ACM-ICPC Japan Alumni Group Summer Camp 2010 , Day 2, Tokyo, Japan, 2010-09-18
http://acm-icpc.aitea.net/