結果

問題 No.2376 障害物競プロ
ユーザー titia
提出日時 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])
0