結果
問題 | No.2376 障害物競プロ |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
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) < 0flg2 = cross3(b1, b2, a1) * cross3(b1, b2, a2) < 0return flg1 and flg2def dot_dist(a, b):dx = a[0] - b[0]dy = a[1] - b[1]return (dx**2 + dy**2) ** 0.5def 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] ** 2if 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 0ret = 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 retn, 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 = Truefor k in range(0, 2 * n, 2):if i // 2 == k // 2 or j // 2 == k // 2:continueif iscross(XY[i], XY[j], XY[k], XY[k + 1]):ok = Falsebreakif 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 - 1j = 2 * (c - 1) + d - 1print(dist[i][j])