結果

問題 No.2376 障害物競プロ
ユーザー KowerKoint2010KowerKoint2010
提出日時 2023-07-03 17:08:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,730 ms / 4,000 ms
コード長 1,548 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 80,408 KB
最終ジャッジ日時 2024-07-17 14:42:36
合計ジャッジ時間 85,809 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    n, m = map(int, input().split())
    xy = [1+1j] * (n*2)
    for i in range(n):
        x0, y0, x1, y1 = map(int, input().split())
        xy[i*2] = x0 + y0*1j
        xy[i*2+1] = x1 + y1*1j

    def segment_intersect(p1, p2, q1, q2):
        p1s = ((q2-q1).conjugate()*(p1-q1)).imag
        p2s = ((q2-q1).conjugate()*(p2-q1)).imag
        q1s = ((p2-p1).conjugate()*(q1-p1)).imag
        q2s = ((p2-p1).conjugate()*(q2-p1)).imag
        if q1s == 0 and q2s == 0:
            return False
        if (((q1s > 0) - (q1s < 0)) == ((q2s > 0) - (q2s < 0))):
            return False
        if (((p1s > 0) - (p1s < 0)) == ((p2s > 0) - (p2s < 0))):
            return False
        return True

    dist = [[1e9] * (n*2) for _ in range(n*2)]
    for i in range(n*2):
        for j in range(n*2):
            if i == j:
                dist[i][j] = 0
                continue
            if ((i>>1) == (j>>1)):
                continue
            ok = True
            for k in range(n):
                if(k == (i>>1) or k == (j>>1)):
                    continue
                ok &= not(segment_intersect(xy[i], xy[j], xy[k*2], xy[k*2+1]))
            if ok:
                dist[i][j] = abs(xy[i]-xy[j])
    for k in range(n*2):
        for i in range(n*2):
            for j in range(n*2):
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
    for _ in range(m):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        c -= 1
        d -= 1
        print(dist[a*2+b][c*2+d])

main()
0