結果
問題 | No.2376 障害物競プロ |
ユーザー |
|
提出日時 | 2023-07-07 23:03:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,338 ms / 4,000 ms |
コード長 | 1,384 bytes |
コンパイル時間 | 298 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 81,128 KB |
最終ジャッジ日時 | 2024-07-21 19:25:53 |
合計ジャッジ時間 | 88,861 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
def intersect(p1, p2, p3, p4):tc1 = (p1[0] - p2[0]) * (p3[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p3[0])tc2 = (p1[0] - p2[0]) * (p4[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p4[0])td1 = (p3[0] - p4[0]) * (p1[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p1[0])td2 = (p3[0] - p4[0]) * (p2[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p2[0])return tc1*tc2 < 0 and td1*td2 < 0N, M = map(int, input().split())xyxy = [tuple(map(int, input().split())) for i in range(N)]def dist(a, b, c, d):return ((xyxy[a][0+b*2]-xyxy[c][0+d*2])**2+(xyxy[a][1+b*2]-xyxy[c][1+d*2])**2)**0.5w = [[10**18 for j in range(2*N)] for i in range(2*N)]for i in range(2*N):for j in range(i, 2*N):if i == j:w[i][j] = 0continuea, b, c, d = i//2, i % 2, j//2, j % 2p1 = (xyxy[a][0+b*2], xyxy[a][1+b*2])p2 = (xyxy[c][0+d*2], xyxy[c][1+d*2])for k in range(N):p3 = (xyxy[k][0], xyxy[k][1])p4 = (xyxy[k][2], xyxy[k][3])if intersect(p1, p2, p3, p4):breakelse:w[i][j] = dist(a, b, c, d)w[j][i] = w[i][j]for k in range(2*N):for i in range(2*N):for j in range(2*N):w[i][j]=min(w[i][j],w[i][k]+w[k][j])for i in range(M):a,b,c,d=map(lambda x:int(x)-1,input().split())print(w[2*a+b][2*c+d])