結果

問題 No.2376 障害物競プロ
ユーザー 👑 seekworserseekworser
提出日時 2023-06-17 04:07:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,729 ms / 4,000 ms
コード長 1,799 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 84,520 KB
最終ジャッジ日時 2024-07-22 12:25:57
合計ジャッジ時間 92,018 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
52,736 KB
testcase_01 AC 43 ms
52,608 KB
testcase_02 AC 47 ms
53,376 KB
testcase_03 AC 42 ms
52,608 KB
testcase_04 AC 634 ms
78,116 KB
testcase_05 AC 954 ms
78,760 KB
testcase_06 AC 666 ms
79,232 KB
testcase_07 AC 1,816 ms
80,284 KB
testcase_08 AC 1,864 ms
80,052 KB
testcase_09 AC 1,721 ms
80,756 KB
testcase_10 AC 1,704 ms
80,572 KB
testcase_11 AC 1,675 ms
81,144 KB
testcase_12 AC 1,610 ms
80,992 KB
testcase_13 AC 1,709 ms
80,800 KB
testcase_14 AC 1,710 ms
80,276 KB
testcase_15 AC 1,513 ms
79,776 KB
testcase_16 AC 1,722 ms
80,468 KB
testcase_17 AC 1,701 ms
81,924 KB
testcase_18 AC 1,683 ms
81,732 KB
testcase_19 AC 2,240 ms
83,460 KB
testcase_20 AC 2,378 ms
84,212 KB
testcase_21 AC 2,386 ms
84,520 KB
testcase_22 AC 1,354 ms
79,252 KB
testcase_23 AC 1,147 ms
79,336 KB
testcase_24 AC 582 ms
76,288 KB
testcase_25 AC 436 ms
78,428 KB
testcase_26 AC 642 ms
76,416 KB
testcase_27 AC 676 ms
78,544 KB
testcase_28 AC 757 ms
79,100 KB
testcase_29 AC 436 ms
78,480 KB
testcase_30 AC 967 ms
79,576 KB
testcase_31 AC 677 ms
78,828 KB
testcase_32 AC 318 ms
79,036 KB
testcase_33 AC 511 ms
79,160 KB
testcase_34 AC 534 ms
79,268 KB
testcase_35 AC 228 ms
78,052 KB
testcase_36 AC 1,349 ms
79,856 KB
testcase_37 AC 1,064 ms
79,288 KB
testcase_38 AC 542 ms
78,160 KB
testcase_39 AC 1,558 ms
79,984 KB
testcase_40 AC 1,091 ms
80,416 KB
testcase_41 AC 467 ms
78,996 KB
testcase_42 AC 2,729 ms
82,916 KB
testcase_43 AC 2,626 ms
81,516 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

COUNTER_CLOCKWISE = 2
CLOCKWISE = -2
ONSEGMENT = 0
ONLINE_BACK = 1
ONLINE_FRONT = -1
def ccw(a, b, c):
    bn = b.copy()
    cn = c.copy()
    bn[0] -= a[0]
    bn[1] -= a[1]
    cn[0] -= a[0]
    cn[1] -= a[1]
    crs = bn[0] * cn[1] - bn[1] * cn[0]
    if (crs < 0):
        return COUNTER_CLOCKWISE
    if (crs > 0):
        return CLOCKWISE
    dot = bn[0] * cn[0] + bn[1] * cn[1]
    normb = bn[0] *+ 2 + bn[1] ** 2
    normc = cn[0] *+ 2 + cn[1] ** 2
    if (dot < 0):
        return ONLINE_BACK
    if (normb < normc):
        return ONLINE_FRONT
    return ONSEGMENT

def intersect(a, b, c, d):
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0

n, m = map(int, input().split())
xy = []
for i in range(n):
    xy.append([])
    x1, y1, x2, y2 = map(int, input().split())
    xy[-1].append([x1, y1])
    xy[-1].append([x2, y2])

adj = [[10 ** 18 for i in range(2 * n)] for i in range(2 * n)]
for i in range(2 * n):
    adj[i][i] = 0
for i in range(2 * n):
    for j in range(2 * n):
        if (i == j):
            continue
        posi = i // 2
        diri = i % 2
        posj = j // 2
        dirj = j % 2
        valid = True
        a = xy[posi][diri]
        b = xy[posj][dirj]
        for k in range(n):
            if (k == posi or k == posj):
                continue
            if (intersect(a, b, xy[k][0], xy[k][1])):
                valid = False
                break
        if (valid):
            adj[i][j] = ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** (1 / 2)
for k in range(2 * n):
    for i in range(2 * n):
        for j in range(2 * n):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])
for i in range(m):
    a,b,c,d = map(int, input().split())
    p1 = (a-1) * 2 + (b-1)
    p2 = (c-1) * 2 + (d-1)
    print(adj[p1][p2])
0