結果

問題 No.2376 障害物競プロ
ユーザー FromBooskaFromBooska
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,120 KB
testcase_01 AC 39 ms
53,248 KB
testcase_02 AC 40 ms
53,888 KB
testcase_03 AC 38 ms
53,248 KB
testcase_04 AC 557 ms
78,816 KB
testcase_05 AC 836 ms
79,068 KB
testcase_06 AC 548 ms
79,068 KB
testcase_07 AC 1,684 ms
80,456 KB
testcase_08 AC 1,579 ms
80,048 KB
testcase_09 AC 1,627 ms
80,796 KB
testcase_10 AC 1,571 ms
81,024 KB
testcase_11 AC 1,554 ms
80,400 KB
testcase_12 AC 1,515 ms
80,708 KB
testcase_13 AC 1,514 ms
80,064 KB
testcase_14 AC 1,662 ms
80,776 KB
testcase_15 AC 1,499 ms
79,504 KB
testcase_16 AC 1,625 ms
80,776 KB
testcase_17 AC 1,573 ms
80,772 KB
testcase_18 AC 1,528 ms
80,268 KB
testcase_19 AC 1,948 ms
82,072 KB
testcase_20 AC 1,878 ms
81,676 KB
testcase_21 AC 1,907 ms
81,668 KB
testcase_22 AC 1,135 ms
79,920 KB
testcase_23 AC 1,023 ms
80,168 KB
testcase_24 AC 553 ms
76,644 KB
testcase_25 AC 412 ms
79,128 KB
testcase_26 AC 631 ms
76,416 KB
testcase_27 AC 644 ms
78,752 KB
testcase_28 AC 648 ms
79,712 KB
testcase_29 AC 416 ms
78,956 KB
testcase_30 AC 1,110 ms
80,152 KB
testcase_31 AC 577 ms
78,568 KB
testcase_32 AC 255 ms
78,832 KB
testcase_33 AC 443 ms
79,268 KB
testcase_34 AC 414 ms
79,704 KB
testcase_35 AC 195 ms
77,440 KB
testcase_36 AC 1,206 ms
79,612 KB
testcase_37 AC 904 ms
79,240 KB
testcase_38 AC 457 ms
79,128 KB
testcase_39 AC 1,338 ms
80,476 KB
testcase_40 AC 901 ms
80,372 KB
testcase_41 AC 433 ms
79,936 KB
testcase_42 AC 1,707 ms
79,952 KB
testcase_43 AC 1,752 ms
80,852 KB
権限があれば一括ダウンロードができます

ソースコード

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