結果
問題 | No.2376 障害物競プロ |
ユーザー | poyon |
提出日時 | 2023-06-19 20:40:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,439 ms / 4,000 ms |
コード長 | 2,404 bytes |
コンパイル時間 | 1,495 ms |
コンパイル使用メモリ | 86,160 KB |
実行使用メモリ | 87,164 KB |
最終ジャッジ日時 | 2023-09-23 07:39:31 |
合計ジャッジ時間 | 79,536 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,376 KB |
testcase_01 | AC | 90 ms
71,260 KB |
testcase_02 | AC | 91 ms
71,204 KB |
testcase_03 | AC | 88 ms
71,120 KB |
testcase_04 | AC | 367 ms
78,716 KB |
testcase_05 | AC | 584 ms
81,604 KB |
testcase_06 | AC | 473 ms
82,240 KB |
testcase_07 | AC | 1,060 ms
83,112 KB |
testcase_08 | AC | 1,069 ms
83,540 KB |
testcase_09 | AC | 1,096 ms
82,352 KB |
testcase_10 | AC | 1,056 ms
83,024 KB |
testcase_11 | AC | 1,170 ms
85,632 KB |
testcase_12 | AC | 1,162 ms
87,164 KB |
testcase_13 | AC | 967 ms
83,088 KB |
testcase_14 | AC | 1,041 ms
82,048 KB |
testcase_15 | AC | 983 ms
82,796 KB |
testcase_16 | AC | 1,061 ms
81,976 KB |
testcase_17 | AC | 1,150 ms
83,332 KB |
testcase_18 | AC | 1,176 ms
86,748 KB |
testcase_19 | AC | 1,439 ms
81,464 KB |
testcase_20 | AC | 1,383 ms
80,628 KB |
testcase_21 | AC | 1,429 ms
81,104 KB |
testcase_22 | AC | 786 ms
81,396 KB |
testcase_23 | AC | 731 ms
81,180 KB |
testcase_24 | AC | 310 ms
77,676 KB |
testcase_25 | AC | 304 ms
79,316 KB |
testcase_26 | AC | 327 ms
77,492 KB |
testcase_27 | AC | 460 ms
81,420 KB |
testcase_28 | AC | 559 ms
83,488 KB |
testcase_29 | AC | 384 ms
81,296 KB |
testcase_30 | AC | 711 ms
83,672 KB |
testcase_31 | AC | 491 ms
82,320 KB |
testcase_32 | AC | 320 ms
81,348 KB |
testcase_33 | AC | 443 ms
82,340 KB |
testcase_34 | AC | 416 ms
82,192 KB |
testcase_35 | AC | 176 ms
77,780 KB |
testcase_36 | AC | 822 ms
82,168 KB |
testcase_37 | AC | 683 ms
83,084 KB |
testcase_38 | AC | 422 ms
81,384 KB |
testcase_39 | AC | 966 ms
82,224 KB |
testcase_40 | AC | 738 ms
82,060 KB |
testcase_41 | AC | 391 ms
82,720 KB |
testcase_42 | AC | 1,320 ms
82,360 KB |
testcase_43 | AC | 1,358 ms
81,796 KB |
ソースコード
import math import sys input = sys.stdin.readline class Point: def __init__(self, x=0, y=0): self.x = x self.y = y def __iadd__(self, v): self.x += v.x self.y += v.y return self def __isub__(self, v): self.x -= v.x self.y -= v.y return self def __add__(self, v): return Point(self.x + v.x, self.y + v.y) def __sub__(self, v): return Point(self.x - v.x, self.y - v.y) def norm(a): return a.x * a.x + a.y * a.y def dot(a, b): return a.x * b.x + a.y * b.y def cross(a, b): return a.x * b.y - a.y * b.x def ccw(p0, p1, p2): a = p1 - p0 b = p2 - p0 if (cross(a, b) > 0): return 1 if (cross(a, b) < 0): return -1 if (dot(a, b) < 0): return 2 if (norm(a) < norm(b)): return -2 return 0 def is_intersected(p1, p2, p3, p4): return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) and \ (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0) def on_segment(p1, p2, p): return ccw(p1, p2, p) == 0 def main(): N, M = map(int, input().split()) x = [[0] * 2 for _ in range(N)] y = [[0] * 2 for _ in range(N)] for i in range(N): x[i][0], y[i][0], x[i][1], y[i][1] = map(int, input().split()) N2 = N * 2 inf = (1 << 30) G = [[inf] * N2 for _ in range(N2)] for i in range(N2): G[i][i] = 0 a, b = divmod(i, 2) x1 = x[a][b] y1 = y[a][b] p1 = Point(x1, y1) for j in range(i + 1, N2): c, d = divmod(j, 2) x2 = x[c][d] y2 = y[c][d] p2 = Point(x2, y2) ok = True for k in range(N): if k == a or k == c: continue p3 = Point(x[k][0], y[k][0]) p4 = Point(x[k][1], y[k][1]) if is_intersected(p1, p2, p3, p4): ok = False break if ok: G[i][j] = G[j][i] = math.hypot(x2 - x1, y2 - y1) for k in range(N2): for i in range(N2): for j in range(N2): G[i][j] = min(G[i][j], G[i][k] + G[k][j]) for i in range(M): a, b, c, d = map(int, input().split()) a -= 1 b -= 1 c -= 1 d -= 1 s = 2 * a + b t = 2 * c + d ans = G[s][t] print(ans) if __name__ == "__main__": main()