結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-15 06:52:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,948 ms / 4,000 ms |
コード長 | 3,669 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 82,072 KB |
最終ジャッジ日時 | 2024-09-16 15:18:19 |
合計ジャッジ時間 | 85,767 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
# 公式解説より# ワーシャルフロイド、ある2点が他の線分と交差しなければ辺を張る# 線分同士の交差判定、外積、ABC016D# https://tjkendev.github.io/procon-library/python/geometry/segment_line_intersection.html# 線分同士の交点判定def dot3(O, A, B):ox, oy = O; ax, ay = A; bx, by = Breturn (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)def cross3(O, A, B):ox, oy = O; ax, ay = A; bx, by = Breturn (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)def dist2(A, B):ax, ay = A; bx, by = Breturn (ax - bx) ** 2 + (ay - by) ** 2def is_intersection(P0, P1, Q0, Q1):C0 = cross3(P0, P1, Q0)C1 = cross3(P0, P1, Q1)D0 = cross3(Q0, Q1, P0)D1 = cross3(Q0, Q1, P1)if C0 == C1 == 0:E0 = dot3(P0, P1, Q0)E1 = dot3(P0, P1, Q1)if not E0 < E1:E0, E1 = E1, E0return E0 <= dist2(P0, P1) and 0 <= E1return C0 * C1 <= 0 and D0 * D1 <= 0#is_intersection((-1, 1), (2, 2), (1, 1), (3, 0))N, M = map(int, input().split())logs = []for i in range(N):x1, y1, x2, y2 = map(int, input().split())logs.append([[x1, y1], [x2, y2]])INF = 10**8distance = [[INF]*(N*2) for i in range(N*2)]for i in range(N*2):distance[i][i] = 0for i in range(N):for j in range(i+1, N):# i0 to j0test1 = Truefor k in range(N):if k==i or k==j:continueif is_intersection(logs[i][0], logs[j][0], logs[k][0], logs[k][1]) == True:test1 = Falseif test1 == True:distance[i*2][j*2] = ((logs[i][0][0]-logs[j][0][0])**2+(logs[i][0][1]-logs[j][0][1])**2)**0.5distance[j*2][i*2] = ((logs[i][0][0]-logs[j][0][0])**2+(logs[i][0][1]-logs[j][0][1])**2)**0.5# i0 to j1test2 = Truefor k in range(N):if k==i or k==j:continueif is_intersection(logs[i][0], logs[j][1], logs[k][0], logs[k][1]) == True:test2 = Falseif test2 == True:distance[i*2][j*2+1] = ((logs[i][0][0]-logs[j][1][0])**2+(logs[i][0][1]-logs[j][1][1])**2)**0.5distance[j*2+1][i*2] = ((logs[i][0][0]-logs[j][1][0])**2+(logs[i][0][1]-logs[j][1][1])**2)**0.5# i1 to j0test3 = Truefor k in range(N):if k==i or k==j:continueif is_intersection(logs[i][1], logs[j][0], logs[k][0], logs[k][1]) == True:test3 = Falseif test3 == True:distance[i*2+1][j*2] = ((logs[i][1][0]-logs[j][0][0])**2+(logs[i][1][1]-logs[j][0][1])**2)**0.5distance[j*2][i*2+1] = ((logs[i][1][0]-logs[j][0][0])**2+(logs[i][1][1]-logs[j][0][1])**2)**0.5# i1 to j1test4 = Truefor k in range(N):if k==i or k==j:continueif is_intersection(logs[i][1], logs[j][1], logs[k][0], logs[k][1]) == True:test4 = Falseif test4 == True:distance[i*2+1][j*2+1] = ((logs[i][1][0]-logs[j][1][0])**2+(logs[i][1][1]-logs[j][1][1])**2)**0.5distance[j*2+1][i*2+1] = ((logs[i][1][0]-logs[j][1][0])**2+(logs[i][1][1]-logs[j][1][1])**2)**0.5#print('i', i, 'j', j, test1, test2, test3, test4)#for d in distance:# print(d)for k in range(N*2):for x in range(N*2):for y in range(N*2):distance[x][y] = min(distance[x][y], distance[x][k] + distance[k][y])#print(distance)for m in range(M):a, b, c, d = map(int, input().split())d = distance[(a-1)*2+(b-1)][(c-1)*2+(d-1)]print(d)