結果

問題 No.2376 障害物競プロ
ユーザー titiatitia
提出日時 2023-07-19 04:05:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,340 ms / 4,000 ms
コード長 3,038 bytes
コンパイル時間 870 ms
コンパイル使用メモリ 81,380 KB
実行使用メモリ 79,908 KB
最終ジャッジ日時 2023-10-19 07:02:28
合計ジャッジ時間 82,033 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,540 KB
testcase_01 AC 44 ms
52,652 KB
testcase_02 AC 43 ms
53,124 KB
testcase_03 AC 43 ms
52,648 KB
testcase_04 AC 594 ms
76,476 KB
testcase_05 AC 842 ms
77,740 KB
testcase_06 AC 453 ms
77,648 KB
testcase_07 AC 1,101 ms
79,020 KB
testcase_08 AC 1,075 ms
78,700 KB
testcase_09 AC 1,098 ms
78,276 KB
testcase_10 AC 1,068 ms
78,676 KB
testcase_11 AC 1,071 ms
78,928 KB
testcase_12 AC 1,022 ms
78,576 KB
testcase_13 AC 1,024 ms
78,916 KB
testcase_14 AC 1,049 ms
78,472 KB
testcase_15 AC 1,044 ms
78,344 KB
testcase_16 AC 1,075 ms
78,612 KB
testcase_17 AC 1,007 ms
78,816 KB
testcase_18 AC 1,045 ms
78,540 KB
testcase_19 AC 1,280 ms
79,204 KB
testcase_20 AC 1,340 ms
79,908 KB
testcase_21 AC 1,297 ms
79,684 KB
testcase_22 AC 879 ms
78,504 KB
testcase_23 AC 641 ms
78,040 KB
testcase_24 AC 605 ms
75,988 KB
testcase_25 AC 369 ms
76,688 KB
testcase_26 AC 648 ms
76,000 KB
testcase_27 AC 622 ms
77,428 KB
testcase_28 AC 519 ms
78,300 KB
testcase_29 AC 387 ms
77,492 KB
testcase_30 AC 475 ms
78,196 KB
testcase_31 AC 463 ms
77,740 KB
testcase_32 AC 207 ms
77,580 KB
testcase_33 AC 332 ms
77,484 KB
testcase_34 AC 316 ms
77,620 KB
testcase_35 AC 189 ms
76,544 KB
testcase_36 AC 711 ms
78,320 KB
testcase_37 AC 804 ms
77,668 KB
testcase_38 AC 385 ms
77,672 KB
testcase_39 AC 879 ms
78,696 KB
testcase_40 AC 413 ms
78,236 KB
testcase_41 AC 368 ms
77,556 KB
testcase_42 AC 1,331 ms
78,224 KB
testcase_43 AC 1,325 ms
78,584 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