結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
52,736 KB
testcase_01 AC 43 ms
52,992 KB
testcase_02 AC 44 ms
53,376 KB
testcase_03 AC 47 ms
52,736 KB
testcase_04 AC 589 ms
76,984 KB
testcase_05 AC 806 ms
78,072 KB
testcase_06 AC 453 ms
77,672 KB
testcase_07 AC 1,074 ms
79,420 KB
testcase_08 AC 1,055 ms
79,400 KB
testcase_09 AC 1,057 ms
78,524 KB
testcase_10 AC 1,043 ms
78,888 KB
testcase_11 AC 1,033 ms
79,356 KB
testcase_12 AC 982 ms
78,856 KB
testcase_13 AC 1,024 ms
79,304 KB
testcase_14 AC 1,096 ms
79,524 KB
testcase_15 AC 977 ms
78,964 KB
testcase_16 AC 1,059 ms
79,224 KB
testcase_17 AC 1,009 ms
78,840 KB
testcase_18 AC 995 ms
79,652 KB
testcase_19 AC 1,255 ms
79,964 KB
testcase_20 AC 1,309 ms
80,612 KB
testcase_21 AC 1,302 ms
80,228 KB
testcase_22 AC 866 ms
78,832 KB
testcase_23 AC 650 ms
78,580 KB
testcase_24 AC 579 ms
76,928 KB
testcase_25 AC 366 ms
76,928 KB
testcase_26 AC 644 ms
76,288 KB
testcase_27 AC 615 ms
78,004 KB
testcase_28 AC 486 ms
79,488 KB
testcase_29 AC 390 ms
77,848 KB
testcase_30 AC 488 ms
78,280 KB
testcase_31 AC 454 ms
78,388 KB
testcase_32 AC 202 ms
78,300 KB
testcase_33 AC 291 ms
77,912 KB
testcase_34 AC 318 ms
78,352 KB
testcase_35 AC 195 ms
77,184 KB
testcase_36 AC 683 ms
79,100 KB
testcase_37 AC 781 ms
78,288 KB
testcase_38 AC 382 ms
78,252 KB
testcase_39 AC 861 ms
78,752 KB
testcase_40 AC 424 ms
78,580 KB
testcase_41 AC 375 ms
78,700 KB
testcase_42 AC 1,321 ms
78,628 KB
testcase_43 AC 1,321 ms
78,908 KB
権限があれば一括ダウンロードができます

ソースコード

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