結果

問題 No.2376 障害物競プロ
コンテスト
ユーザー rin204
提出日時 2023-07-07 21:48:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,103 ms / 4,000 ms
コード長 1,816 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 82,000 KB
最終ジャッジ日時 2024-09-25 08:26:24
合計ジャッジ時間 87,546 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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