結果

問題 No.2376 障害物競プロ
ユーザー 👑 rin204rin204
提出日時 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])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0