結果

問題 No.2376 障害物競プロ
ユーザー titiatitia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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/012837
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<0
POINTS=[]
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]]=i
Distance=[[float("inf") for i in range(len(POINTS))] for j in range(len(POINTS))]
for i in range(len(POINTS)):
Distance[i][i]=0
for i in range(N):
x0,y0,z0,w0=L[i]
for j in range(N):
x1,y1,z1,w1=L[j]
flag=1
p1=(x0,y0)
p2=(x1,y1)
for k in range(N):
if i==k or j==k:
continue
x2,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=0
break
if flag==1:
u=D[p1]
v=D[p2]
dis=((x0-x1)**2+(y0-y1)**2)**(1/2)
Distance[u][v]=dis
Distance[v][u]=dis
flag=1
p1=(x0,y0)
p2=(z1,w1)
for k in range(N):
if i==k or j==k:
continue
x2,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=0
break
if flag==1:
u=D[p1]
v=D[p2]
dis=((x0-z1)**2+(y0-w1)**2)**(1/2)
Distance[u][v]=dis
Distance[v][u]=dis
flag=1
p1=(z0,w0)
p2=(z1,w1)
for k in range(N):
if i==k or j==k:
continue
x2,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=0
break
if flag==1:
u=D[p1]
v=D[p2]
dis=((z0-z1)**2+(w0-w1)**2)**(1/2)
Distance[u][v]=dis
Distance[v][u]=dis
for 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]=length
for i in range(M):
x,y,z,w=map(int,input().split())
u=(x-1)*2+y-1
v=(z-1)*2+w-1
print(Distance[u][v])
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0