結果

問題 No.2376 障害物競プロ
ユーザー lam6er
提出日時 2025-03-26 15:50:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,108 ms / 4,000 ms
コード長 2,705 bytes
コンパイル時間 256 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 146,196 KB
最終ジャッジ日時 2025-03-26 15:52:05
合計ジャッジ時間 62,301 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def segments_intersect(a, b, c, d):
    ax, ay = a
    bx, by = b
    cx, cy = c
    dx, dy = d

    # Calculate the direction vectors
    v1x = bx - ax
    v1y = by - ay
    v2x = dx - cx
    v2y = dy - cy

    # Calculate the denominator
    denominator = v1x * v2y - v1y * v2x

    if denominator == 0:
        return False

    # Calculate parameters s and t
    s_numerator = (cx - ax) * v1y - (cy - ay) * v1x
    t_numerator = (cx - ax) * v2y - (cy - ay) * v2x

    s = s_numerator / denominator
    t = t_numerator / denominator

    return 0 < s < 1 and 0 < t < 1

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr +=2

    logs = []
    nodes = []
    for i in range(N):
        x1 = int(input[ptr])
        y1 = int(input[ptr+1])
        x2 = int(input[ptr+2])
        y2 = int(input[ptr+3])
        ptr +=4
        logs.append( ( (x1, y1), (x2, y2) ) )
        nodes.append( (x1, y1) )
        nodes.append( (x2, y2) )

    V = len(nodes)
    INF = float('inf')

    # Build adjacency list
    graph = [[] for _ in range(V)]
    for u in range(V):
        for v in range(V):
            if u == v:
                continue
            # Check if u and v are endpoints of the same log
            if (u // 2) == (v // 2):
                continue
            a = nodes[u]
            b = nodes[v]
            valid = True
            for log in logs:
                c, d = log
                if segments_intersect(a, b, c, d):
                    valid = False
                    break
            if valid:
                dx = a[0] - b[0]
                dy = a[1] - b[1]
                distance = (dx**2 + dy**2)**0.5
                graph[u].append( (v, distance) )

    # Precompute shortest paths using Dijkstra's algorithm
    shortest = []
    for s in range(V):
        dist = [INF] * V
        dist[s] = 0.0
        heap = []
        heapq.heappush(heap, (0.0, s))
        while heap:
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, w in graph[u]:
                if dist[v] > d + w:
                    dist[v] = d + w
                    heapq.heappush(heap, (dist[v], v))
        shortest.append(dist)

    # Process queries
    output = []
    for _ in range(M):
        a = int(input[ptr])
        b = int(input[ptr+1])
        c = int(input[ptr+2])
        d = int(input[ptr+3])
        ptr +=4
        start = 2 * (a - 1) + (b - 1)
        end = 2 * (c - 1) + (d - 1)
        res = shortest[start][end]
        output.append("{0:.12f}".format(res))

    print('\n'.join(output))

if __name__ == "__main__":
    main()
0