結果

問題 No.2376 障害物競プロ
ユーザー 👑 rin204rin204
提出日時 2023-07-07 21:48:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,959 ms / 4,000 ms
コード長 1,816 bytes
コンパイル時間 2,664 ms
コンパイル使用メモリ 80,544 KB
実行使用メモリ 81,524 KB
最終ジャッジ日時 2023-10-26 00:27:34
合計ジャッジ時間 91,203 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,392 KB
testcase_01 AC 39 ms
52,536 KB
testcase_02 AC 40 ms
53,344 KB
testcase_03 AC 38 ms
52,532 KB
testcase_04 AC 570 ms
77,916 KB
testcase_05 AC 804 ms
76,888 KB
testcase_06 AC 519 ms
77,472 KB
testcase_07 AC 1,467 ms
79,032 KB
testcase_08 AC 1,476 ms
79,112 KB
testcase_09 AC 1,457 ms
78,848 KB
testcase_10 AC 1,482 ms
78,604 KB
testcase_11 AC 1,535 ms
79,652 KB
testcase_12 AC 1,480 ms
79,088 KB
testcase_13 AC 1,442 ms
79,400 KB
testcase_14 AC 1,390 ms
78,876 KB
testcase_15 AC 1,319 ms
78,588 KB
testcase_16 AC 1,378 ms
78,956 KB
testcase_17 AC 1,451 ms
78,888 KB
testcase_18 AC 1,464 ms
79,112 KB
testcase_19 AC 1,468 ms
80,148 KB
testcase_20 AC 1,890 ms
81,340 KB
testcase_21 AC 1,888 ms
81,524 KB
testcase_22 AC 1,094 ms
79,008 KB
testcase_23 AC 892 ms
78,644 KB
testcase_24 AC 534 ms
76,012 KB
testcase_25 AC 344 ms
76,964 KB
testcase_26 AC 583 ms
76,008 KB
testcase_27 AC 576 ms
77,376 KB
testcase_28 AC 705 ms
78,452 KB
testcase_29 AC 366 ms
77,448 KB
testcase_30 AC 704 ms
78,612 KB
testcase_31 AC 523 ms
78,224 KB
testcase_32 AC 201 ms
77,060 KB
testcase_33 AC 374 ms
77,812 KB
testcase_34 AC 399 ms
78,480 KB
testcase_35 AC 188 ms
76,356 KB
testcase_36 AC 1,091 ms
78,824 KB
testcase_37 AC 887 ms
78,100 KB
testcase_38 AC 416 ms
77,372 KB
testcase_39 AC 1,265 ms
78,764 KB
testcase_40 AC 899 ms
79,024 KB
testcase_41 AC 357 ms
77,552 KB
testcase_42 AC 1,959 ms
80,624 KB
testcase_43 AC 1,953 ms
81,456 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def cross3(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])


def iscross(a1, a2, b1, b2):
    flg1 = cross3(a1, a2, b1) * cross3(a1, a2, b2) < 0
    flg2 = cross3(b1, b2, a1) * cross3(b1, b2, a2) < 0
    return flg1 and flg2


def dot_dist(a, b):
    dx = a[0] - b[0]
    dy = a[1] - b[1]
    return (dx**2 + dy**2) ** 0.5


def dot_line_dist(p, a, b):
    d0 = (b[0] - a[0], b[1] - a[1])
    d1 = (p[0] - a[0], p[1] - a[1])
    dot = d0[0] * d1[0] + d0[1] * d1[1]
    dd = d0[0] ** 2 + d0[1] ** 2
    if 0 <= dot <= dd:
        cross = d0[0] * d1[1] - d0[1] * d1[0]
        return abs(cross) / (dd**0.5)
    else:
        return min(dot_dist(p, a), dot_dist(p, b))


def line_dist(a1, a2, b1, b2):
    if iscross(a1, a2, b1, b2):
        return 0
    ret = dot_line_dist(a1, b1, b2)
    ret = min(ret, dot_line_dist(a2, b1, b2))
    ret = min(ret, dot_line_dist(b1, a1, a2))
    ret = min(ret, dot_line_dist(b2, a1, a2))
    return ret


n, m = map(int, input().split())
XY = []
for _ in range(n):
    x, y, z, a = map(int, input().split())
    XY.append((x, y))
    XY.append((z, a))

dist = [[1 << 60] * (2 * n) for _ in range(2 * n)]
for i in range(2 * n):
    for j in range(2 * n):
        ok = True
        for k in range(0, 2 * n, 2):
            if i // 2 == k // 2 or j // 2 == k // 2:
                continue
            if iscross(XY[i], XY[j], XY[k], XY[k + 1]):
                ok = False
                break

        if ok:
            dist[i][j] = dot_dist(XY[i], XY[j])


for k in range(2 * n):
    for i in range(2 * n):
        for j in range(2 * n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


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