Problem:


Problem E: 街を駆ける道

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

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

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

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

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

入力の１行目には、整数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）が、空白区切りで書かれている。ネーヴァ王国の地理は２次元直交座標平面であらわされ、１＋ i 行目に書かれた整数xA,i とyA,i は、トタタ族が暮らすi 番目の街の位置座標が(xA,i, yA,i) であることをあらわす。(xA,1, yA,1) と(xA,2, yA,2) が、結ぶべき２つの街の座標である。

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

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

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



Sample input:
2 2
0 0
1 1
2 0
2 -1


Sample output:
2.414213562373

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from math import sqrt
import sys
readline = sys.stdin.buffer.readline
write = sys.stdout.write
N, M = map(int, readline().split())
PS = [list(map(int, readline().split())) for i in range(N)]
QS = [list(map(int, readline().split())) for i in range(M)]

def dot3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
    ax, ay = A; bx, by = B
    return (ax - bx) ** 2 + (ay - by) ** 2
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        E0 = dot3(P0, P1, Q0)
        E1 = dot3(P0, P1, Q1)
        if not E0 < E1:
            E0, E1 = E1, E0
        return E0 <= dist2(P0, P1) and 0 <= E1
    return C0 * C1 <= 0 and D0 * D1 <= 0

def solve(N, PS, q0, q1):
    yield 10**18
    p0 = PS[0]; p1 = PS[1]
    if not is_intersection(p0, p1, q0, q1):
        yield sqrt(dist2(p0, p1))
        return
    V0 = [i for i in range(2, N) if not is_intersection(p0, PS[i], q0, q1)]
    V1 = [i for i in range(2, N) if not is_intersection(p1, PS[i], q0, q1)]
    D0 = [sqrt(dist2(p0, p)) for p in PS]
    D1 = [sqrt(dist2(p1, p)) for p in PS]
    for v0 in V0:
        for v1 in V1:
            if v0 != v1:
                if is_intersection(PS[v0], PS[v1], q0, q1):
                    continue
                yield D0[v0] + D1[v1] + sqrt(dist2(PS[v0], PS[v1]))
            else:
                yield D0[v0] + D1[v1]

ans = min(
        sqrt(dist2(QS[0], QS[1])) + min(solve(N, PS, QS[0], QS[1])),
        sqrt(dist2(PS[0], PS[1])) + min(solve(M, QS, PS[0], PS[1]))
        )
if ans < 10**9:
    write("%.16f\n" % ans)
else:
    write("-1\n")

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def _kosa(a1, a2, b1, b2):
    x1,y1 = a1
    x2,y2 = a2
    x3,y3 = b1
    x4,y4 = b2

    tc = (x1-x2)*(y3-y1)+(y1-y2)*(x1-x3)
    td = (x1-x2)*(y4-y1)+(y1-y2)*(x1-x4)
    return tc*td < 0

def kosa(a1, a2, b1, b2):
    return _kosa(a1,a2,b1,b2) and _kosa(b1,b2,a1,a2)

def distance(x1, y1, x2, y2):
    return math.sqrt((x1-x2)**2 + (y1-y2)**2)

def distance_p(a, b):
    return distance(a[0], a[1], b[0], b[1])

def main():
    rr = []

    def f(n,m):
        a = [LI() for _ in range(n)]
        b = [LI() for _ in range(m)]

        def search(a,b1,b2,rg):
            d = collections.defaultdict(lambda: inf)
            s = 0
            t = 1
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True
                if u == t:
                    return d[u]

                for uv in rg:
                    if v[uv]:
                        continue
                    if kosa(a[u],a[uv], b1,b2):
                        continue
                    ud = distance_p(a[u],a[uv])
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return -1

        ad = distance_p(a[0], a[1])
        bd = distance_p(b[0], b[1])
        ar = search(a,b[0],b[1],list(range(1,n)))
        br = search(b,a[0],a[1],list(range(1,m)))
        r = -1
        if ar < 0:
            if br < 0:
                return r
            return '{:0.9f}'.format(br + ad)
        if br < 0:
            return '{:0.9f}'.format(ar + bd)

        return '{:0.9f}'.format(min(ar + bd, br + ad))

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        # print(n, rr[-1])
        break

    return '\n'.join(map(str, rr))


print(main())