結果
問題 | No.2376 障害物競プロ |
ユーザー |
![]() |
提出日時 | 2023-07-19 04:05:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,321 ms / 4,000 ms |
コード長 | 3,038 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 80,612 KB |
最終ジャッジ日時 | 2024-09-19 03:22:22 |
合計ジャッジ時間 | 74,392 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
N,M=map(int,input().split())L=[list(map(int,input().split())) for i in range(N)]#P=[list(map(int,input().split())) for i in range(M)]# https://www.st-hakky-blog.com/entry/2018/09/05/012837def 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<0POINTS=[]for x1,y1,x2,y2 in L:POINTS.append((x1,y1))POINTS.append((x2,y2))D=dict()for i in range(len(POINTS)):D[POINTS[i]]=iDistance=[[float("inf") for i in range(len(POINTS))] for j in range(len(POINTS))]for i in range(len(POINTS)):Distance[i][i]=0for i in range(N):x0,y0,z0,w0=L[i]for j in range(N):x1,y1,z1,w1=L[j]flag=1p1=(x0,y0)p2=(x1,y1)for k in range(N):if i==k or j==k:continuex2,y2,z2,w2=L[k]p3=(x2,y2)p4=(z2,w2)#print(p1,p2,p3,p4,intersect(p1, p2, p3, p4))if intersect(p1, p2, p3, p4)==True:flag=0breakif flag==1:u=D[p1]v=D[p2]dis=((x0-x1)**2+(y0-y1)**2)**(1/2)Distance[u][v]=disDistance[v][u]=disflag=1p1=(x0,y0)p2=(z1,w1)for k in range(N):if i==k or j==k:continuex2,y2,z2,w2=L[k]p3=(x2,y2)p4=(z2,w2)#print(p1,p2,p3,p4,intersect(p1, p2, p3, p4))if intersect(p1, p2, p3, p4)==True:flag=0breakif flag==1:u=D[p1]v=D[p2]dis=((x0-z1)**2+(y0-w1)**2)**(1/2)Distance[u][v]=disDistance[v][u]=disflag=1p1=(z0,w0)p2=(z1,w1)for k in range(N):if i==k or j==k:continuex2,y2,z2,w2=L[k]p3=(x2,y2)p4=(z2,w2)#print(p1,p2,p3,p4,intersect(p1, p2, p3, p4))if intersect(p1, p2, p3, p4)==True:flag=0breakif flag==1:u=D[p1]v=D[p2]dis=((z0-z1)**2+(w0-w1)**2)**(1/2)Distance[u][v]=disDistance[v][u]=disfor k in range(len(POINTS)): # k個までの町を使ってのDisが知れているときにfor i in range(len(POINTS)): # 町iとfor j in range(i,len(POINTS)): # 町jとの最短距離は、length=Distance[i][k]+Distance[j][k]if Distance[i][j]>length:Distance[i][j]=Distance[j][i]=lengthfor i in range(M):x,y,z,w=map(int,input().split())u=(x-1)*2+y-1v=(z-1)*2+w-1print(Distance[u][v])