結果

問題 No.2376 障害物競プロ
ユーザー FromBooskaFromBooska
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#
# 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 = B
return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)
def cross3(O, A, B):
ox, oy = O; ax, ay = A; bx, by = B
return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def dist2(A, B):
ax, ay = A; bx, by = B
return (ax - bx) ** 2 + (ay - by) ** 2
def 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, E0
return E0 <= dist2(P0, P1) and 0 <= E1
return 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**8
distance = [[INF]*(N*2) for i in range(N*2)]
for i in range(N*2):
distance[i][i] = 0
for i in range(N):
for j in range(i+1, N):
# i0 to j0
test1 = True
for k in range(N):
if k==i or k==j:
continue
if is_intersection(logs[i][0], logs[j][0], logs[k][0], logs[k][1]) == True:
test1 = False
if 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.5
distance[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 j1
test2 = True
for k in range(N):
if k==i or k==j:
continue
if is_intersection(logs[i][0], logs[j][1], logs[k][0], logs[k][1]) == True:
test2 = False
if 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.5
distance[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 j0
test3 = True
for k in range(N):
if k==i or k==j:
continue
if is_intersection(logs[i][1], logs[j][0], logs[k][0], logs[k][1]) == True:
test3 = False
if 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.5
distance[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 j1
test4 = True
for k in range(N):
if k==i or k==j:
continue
if is_intersection(logs[i][1], logs[j][1], logs[k][0], logs[k][1]) == True:
test4 = False
if 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.5
distance[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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0