結果

問題 No.2376 障害物競プロ
ユーザー FromBooska
提出日時 2023-07-15 06:52:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,948 ms / 4,000 ms
コード長 3,669 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 82,072 KB
最終ジャッジ日時 2024-09-16 15:18:19
合計ジャッジ時間 85,767 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 公式解説より
# ワーシャルフロイド、ある2点が他の線分と交差しなければ辺を張る
# 線分同士の交差判定、外積、ABC016D

# https://tjkendev.github.io/procon-library/python/geometry/segment_line_intersection.html
# 線分同士の交点判定
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

#is_intersection((-1, 1), (2, 2), (1, 1), (3, 0))

N, M = map(int, input().split())
logs = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    logs.append([[x1, y1], [x2, y2]])

INF = 10**8
distance = [[INF]*(N*2) for i in range(N*2)]
for i in range(N*2):
    distance[i][i] = 0

for i in range(N):
    for j in range(i+1, N):
        # i0 to j0
        test1 = True
        for k in range(N):
            if k==i or k==j:
                continue
            if is_intersection(logs[i][0], logs[j][0], logs[k][0], logs[k][1]) == True:
                test1 = False
        if test1 == True:
            distance[i*2][j*2] = ((logs[i][0][0]-logs[j][0][0])**2+(logs[i][0][1]-logs[j][0][1])**2)**0.5
            distance[j*2][i*2] = ((logs[i][0][0]-logs[j][0][0])**2+(logs[i][0][1]-logs[j][0][1])**2)**0.5
        # i0 to j1
        test2 = True
        for k in range(N):
            if k==i or k==j:
                continue
            if is_intersection(logs[i][0], logs[j][1], logs[k][0], logs[k][1]) == True:
                test2 = False
        if test2 == True:
            distance[i*2][j*2+1] = ((logs[i][0][0]-logs[j][1][0])**2+(logs[i][0][1]-logs[j][1][1])**2)**0.5
            distance[j*2+1][i*2] = ((logs[i][0][0]-logs[j][1][0])**2+(logs[i][0][1]-logs[j][1][1])**2)**0.5
        # i1 to j0
        test3 = True
        for k in range(N):
            if k==i or k==j:
                continue
            if is_intersection(logs[i][1], logs[j][0], logs[k][0], logs[k][1]) == True:
                test3 = False
        if test3 == True:
            distance[i*2+1][j*2] = ((logs[i][1][0]-logs[j][0][0])**2+(logs[i][1][1]-logs[j][0][1])**2)**0.5
            distance[j*2][i*2+1] = ((logs[i][1][0]-logs[j][0][0])**2+(logs[i][1][1]-logs[j][0][1])**2)**0.5       
        # i1 to j1
        test4 = True
        for k in range(N):
            if k==i or k==j:
                continue
            if is_intersection(logs[i][1], logs[j][1], logs[k][0], logs[k][1]) == True:
                test4 = False
        if test4 == True:
            distance[i*2+1][j*2+1] = ((logs[i][1][0]-logs[j][1][0])**2+(logs[i][1][1]-logs[j][1][1])**2)**0.5
            distance[j*2+1][i*2+1] = ((logs[i][1][0]-logs[j][1][0])**2+(logs[i][1][1]-logs[j][1][1])**2)**0.5     

        #print('i', i, 'j', j, test1, test2, test3, test4)
            
#for d in distance:
#    print(d)

for k in range(N*2):
    for x in range(N*2):
        for y in range(N*2):
            distance[x][y] = min(distance[x][y], distance[x][k] + distance[k][y])

#print(distance)

for m in range(M):
    a, b, c, d = map(int, input().split())
    d = distance[(a-1)*2+(b-1)][(c-1)*2+(d-1)]
    print(d)
0