結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-06-13 13:16:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,525 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 82,184 KB |
実行使用メモリ | 85,120 KB |
最終ジャッジ日時 | 2024-07-16 07:23:54 |
合計ジャッジ時間 | 105,705 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 33 WA * 7 |
ソースコード
from math import sqrtN,M=map(int,input().split())xy = []for i in range(N):x1,y1,x2,y2=map(int,input().split())xy.append(((x1,y1),(x2,y2)))#ワーシャルフロイドdp = [[100000000000000000000] * (N + N) for _ in range(N + N)]for i in range(N + N):for j in range(N + N):if i == j:dp[i][j] = 0continuexy1 = xy[i % N][i // N]xy2 = xy[j % N][j // N]flag = Truefor k in range(N):xy3 = xy[k][0]xy4 = xy[k][1]if xy3 in [xy1, xy2] or xy4 in [xy1, xy2]:continues = (xy1[0] - xy2[0]) * (xy3[1] - xy1[1]) - (xy1[1] - xy2[1]) * (xy3[0] - xy1[0])t = (xy1[0] - xy2[0]) * (xy4[1] - xy1[1]) - (xy1[1] - xy2[1]) * (xy4[0] - xy1[0])s2 = (xy3[0] - xy4[0]) * (xy1[1] - xy3[1]) - (xy3[1] - xy4[1]) * (xy1[0] - xy3[0])t2 = (xy3[0] - xy4[0]) * (xy2[1] - xy3[1]) - (xy3[1] - xy4[1]) * (xy2[0] - xy3[0])if not(s * t > 0 or s2 * t2 > 0):flag = Falsebreakif flag:dp[i][j] = sqrt((xy1[0] - xy2[0]) ** 2 + (xy1[1] - xy2[1]) ** 2)for k in range(N + N):for i in range(N + N):for j in range(N + N):dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])for _ in range(M):a,b,c,d=map(int,input().split())print(dp[a-1+(b-1)*N][c-1+(d-1)*N])