結果

問題 No.2376 障害物競プロ
ユーザー 👑 seekworser
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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