結果
問題 |
No.2376 障害物競プロ
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()