結果

問題 No.2376 障害物競プロ
ユーザー FromBooskaFromBooska
提出日時 2023-07-15 06:52:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,005 ms / 4,000 ms
コード長 3,669 bytes
コンパイル時間 537 ms
コンパイル使用メモリ 87,004 KB
実行使用メモリ 84,424 KB
最終ジャッジ日時 2023-10-14 21:33:05
合計ジャッジ時間 98,493 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
71,528 KB
testcase_01 AC 70 ms
71,668 KB
testcase_02 AC 70 ms
71,688 KB
testcase_03 AC 70 ms
71,720 KB
testcase_04 AC 642 ms
78,928 KB
testcase_05 AC 892 ms
81,448 KB
testcase_06 AC 587 ms
81,324 KB
testcase_07 AC 1,715 ms
81,664 KB
testcase_08 AC 1,704 ms
81,976 KB
testcase_09 AC 1,728 ms
83,068 KB
testcase_10 AC 1,698 ms
82,372 KB
testcase_11 AC 1,758 ms
82,332 KB
testcase_12 AC 1,657 ms
82,728 KB
testcase_13 AC 1,864 ms
82,080 KB
testcase_14 AC 1,751 ms
81,812 KB
testcase_15 AC 1,557 ms
81,720 KB
testcase_16 AC 1,635 ms
82,616 KB
testcase_17 AC 1,639 ms
82,192 KB
testcase_18 AC 1,619 ms
83,328 KB
testcase_19 AC 1,995 ms
84,424 KB
testcase_20 AC 2,004 ms
83,588 KB
testcase_21 AC 2,005 ms
83,456 KB
testcase_22 AC 1,284 ms
80,964 KB
testcase_23 AC 1,112 ms
81,184 KB
testcase_24 AC 596 ms
78,652 KB
testcase_25 AC 442 ms
80,936 KB
testcase_26 AC 642 ms
79,076 KB
testcase_27 AC 672 ms
81,540 KB
testcase_28 AC 693 ms
81,280 KB
testcase_29 AC 451 ms
81,656 KB
testcase_30 AC 980 ms
81,484 KB
testcase_31 AC 599 ms
80,928 KB
testcase_32 AC 293 ms
81,300 KB
testcase_33 AC 485 ms
81,412 KB
testcase_34 AC 458 ms
81,316 KB
testcase_35 AC 232 ms
78,180 KB
testcase_36 AC 1,276 ms
81,544 KB
testcase_37 AC 1,000 ms
80,624 KB
testcase_38 AC 518 ms
80,828 KB
testcase_39 AC 1,456 ms
82,340 KB
testcase_40 AC 1,001 ms
82,168 KB
testcase_41 AC 470 ms
80,500 KB
testcase_42 AC 1,799 ms
82,284 KB
testcase_43 AC 1,874 ms
81,736 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