結果

問題 No.2376 障害物競プロ
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:37:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,088 ms / 4,000 ms
コード長 2,671 bytes
コンパイル時間 211 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 143,472 KB
最終ジャッジ日時 2025-03-31 17:39:45
合計ジャッジ時間 60,976 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    ptr +=1
    M = int(data[ptr])
    ptr +=1
    
    original_segments = []
    points = []
    for _ in range(N):
        x1 = int(data[ptr])
        ptr +=1
        y1 = int(data[ptr])
        ptr +=1
        x2 = int(data[ptr])
        ptr +=1
        y2 = int(data[ptr])
        ptr +=1
        original_segments.append( ((x1, y1), (x2, y2)) )
        points.append( (x1, y1) )
        points.append( (x2, y2) )
    
    V = 2 * N
    INF = float('inf')
    
    # Initialize distance matrix
    dist = [[INF] * V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0.0
    
    # CCW function
    def ccw(a, b, c):
        area = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
        if area > 0:
            return 1
        elif area < 0:
            return -1
        else:
            return 0
    
    # Segment intersection check
    def segments_intersect(seg1, seg2):
        a, b = seg1
        c, d = seg2
        ccw1 = ccw(a, b, c)
        ccw2 = ccw(a, b, d)
        if ccw1 * ccw2 >= 0:
            return False
        ccw3 = ccw(c, d, a)
        ccw4 = ccw(c, d, b)
        if ccw3 * ccw4 >= 0:
            return False
        return True
    
    # Populate edges
    for u in range(V):
        for v in range(V):
            if u == v:
                continue
            seg_uv = (points[u], points[v])
            has_intersection = False
            for seg in original_segments:
                if segments_intersect(seg_uv, seg):
                    has_intersection = True
                    break
            if not has_intersection:
                dx = points[u][0] - points[v][0]
                dy = points[u][1] - points[v][1]
                dist[u][v] = math.hypot(dx, dy)
    
    # Floyd-Warshall algorithm
    for k in range(V):
        for i in range(V):
            if dist[i][k] == INF:
                continue
            for j in range(V):
                if dist[k][j] == INF:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Process queries
    output = []
    for _ in range(M):
        a = int(data[ptr])-1
        ptr +=1
        b = int(data[ptr])-1
        ptr +=1
        c = int(data[ptr])-1
        ptr +=1
        d = int(data[ptr])-1
        ptr +=1
        
        s = 2 * a + b
        g = 2 * c + d
        res = dist[s][g]
        output.append("{0:.15f}".format(res))
    
    print('\n'.join(output))

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