結果

問題 No.2376 障害物競プロ
ユーザー 👑 seekworserseekworser
提出日時 2023-06-17 04:07:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,560 ms / 4,000 ms
コード長 1,799 bytes
コンパイル時間 1,932 ms
コンパイル使用メモリ 84,940 KB
実行使用メモリ 86,328 KB
最終ジャッジ日時 2023-09-29 18:24:03
合計ジャッジ時間 96,280 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 73 ms
71,812 KB
testcase_01 AC 74 ms
71,900 KB
testcase_02 AC 76 ms
71,660 KB
testcase_03 AC 73 ms
71,780 KB
testcase_04 AC 638 ms
79,740 KB
testcase_05 AC 940 ms
80,500 KB
testcase_06 AC 674 ms
80,652 KB
testcase_07 AC 1,800 ms
82,548 KB
testcase_08 AC 1,831 ms
83,120 KB
testcase_09 AC 1,723 ms
82,296 KB
testcase_10 AC 1,686 ms
83,012 KB
testcase_11 AC 1,675 ms
82,824 KB
testcase_12 AC 1,598 ms
84,544 KB
testcase_13 AC 1,699 ms
83,892 KB
testcase_14 AC 1,683 ms
81,992 KB
testcase_15 AC 1,629 ms
81,980 KB
testcase_16 AC 1,708 ms
82,120 KB
testcase_17 AC 1,676 ms
83,788 KB
testcase_18 AC 1,633 ms
82,288 KB
testcase_19 AC 2,234 ms
85,668 KB
testcase_20 AC 2,358 ms
85,556 KB
testcase_21 AC 2,403 ms
86,328 KB
testcase_22 AC 1,378 ms
80,924 KB
testcase_23 AC 1,154 ms
82,152 KB
testcase_24 AC 598 ms
78,756 KB
testcase_25 AC 443 ms
79,676 KB
testcase_26 AC 672 ms
78,528 KB
testcase_27 AC 682 ms
80,276 KB
testcase_28 AC 827 ms
81,164 KB
testcase_29 AC 450 ms
80,188 KB
testcase_30 AC 968 ms
81,596 KB
testcase_31 AC 686 ms
81,436 KB
testcase_32 AC 332 ms
81,236 KB
testcase_33 AC 528 ms
81,412 KB
testcase_34 AC 539 ms
80,692 KB
testcase_35 AC 248 ms
80,392 KB
testcase_36 AC 1,365 ms
81,508 KB
testcase_37 AC 1,094 ms
80,744 KB
testcase_38 AC 553 ms
80,688 KB
testcase_39 AC 1,547 ms
81,480 KB
testcase_40 AC 1,086 ms
81,720 KB
testcase_41 AC 493 ms
81,076 KB
testcase_42 AC 2,560 ms
85,000 KB
testcase_43 AC 2,553 ms
84,048 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