結果
問題 | No.960 マンハッタン距離3 |
ユーザー | maspy |
提出日時 | 2020-05-10 06:13:31 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,323 ms / 2,000 ms |
コード長 | 6,278 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 13,568 KB |
実行使用メモリ | 35,620 KB |
最終ジャッジ日時 | 2024-07-06 23:37:22 |
合計ジャッジ時間 | 45,687 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
11,520 KB |
testcase_01 | AC | 27 ms
11,520 KB |
testcase_02 | AC | 27 ms
11,392 KB |
testcase_03 | AC | 26 ms
11,392 KB |
testcase_04 | AC | 27 ms
11,520 KB |
testcase_05 | AC | 27 ms
11,392 KB |
testcase_06 | AC | 27 ms
11,520 KB |
testcase_07 | AC | 31 ms
11,520 KB |
testcase_08 | AC | 29 ms
11,392 KB |
testcase_09 | AC | 29 ms
11,520 KB |
testcase_10 | AC | 29 ms
11,392 KB |
testcase_11 | AC | 27 ms
11,392 KB |
testcase_12 | AC | 27 ms
11,392 KB |
testcase_13 | AC | 26 ms
11,392 KB |
testcase_14 | AC | 29 ms
11,392 KB |
testcase_15 | AC | 27 ms
11,392 KB |
testcase_16 | AC | 26 ms
11,392 KB |
testcase_17 | AC | 27 ms
11,520 KB |
testcase_18 | AC | 29 ms
11,520 KB |
testcase_19 | AC | 26 ms
11,520 KB |
testcase_20 | AC | 29 ms
11,392 KB |
testcase_21 | AC | 29 ms
11,392 KB |
testcase_22 | AC | 26 ms
11,392 KB |
testcase_23 | AC | 26 ms
11,392 KB |
testcase_24 | AC | 27 ms
11,520 KB |
testcase_25 | AC | 27 ms
11,520 KB |
testcase_26 | AC | 28 ms
11,520 KB |
testcase_27 | AC | 27 ms
11,520 KB |
testcase_28 | AC | 27 ms
11,520 KB |
testcase_29 | AC | 28 ms
11,392 KB |
testcase_30 | AC | 28 ms
11,392 KB |
testcase_31 | AC | 27 ms
11,520 KB |
testcase_32 | AC | 26 ms
11,520 KB |
testcase_33 | AC | 27 ms
11,520 KB |
testcase_34 | AC | 28 ms
11,520 KB |
testcase_35 | AC | 26 ms
11,520 KB |
testcase_36 | AC | 28 ms
11,520 KB |
testcase_37 | AC | 27 ms
11,520 KB |
testcase_38 | AC | 29 ms
11,520 KB |
testcase_39 | AC | 27 ms
11,520 KB |
testcase_40 | AC | 28 ms
11,520 KB |
testcase_41 | AC | 27 ms
11,520 KB |
testcase_42 | AC | 27 ms
11,520 KB |
testcase_43 | AC | 27 ms
11,520 KB |
testcase_44 | AC | 27 ms
11,520 KB |
testcase_45 | AC | 27 ms
11,520 KB |
testcase_46 | AC | 27 ms
11,520 KB |
testcase_47 | AC | 27 ms
11,520 KB |
testcase_48 | AC | 27 ms
11,520 KB |
testcase_49 | AC | 28 ms
11,264 KB |
testcase_50 | AC | 26 ms
11,520 KB |
testcase_51 | AC | 27 ms
11,520 KB |
testcase_52 | AC | 27 ms
11,392 KB |
testcase_53 | AC | 27 ms
11,520 KB |
testcase_54 | AC | 27 ms
11,392 KB |
testcase_55 | AC | 27 ms
11,520 KB |
testcase_56 | AC | 26 ms
11,520 KB |
testcase_57 | AC | 27 ms
11,520 KB |
testcase_58 | AC | 26 ms
11,520 KB |
testcase_59 | AC | 27 ms
11,392 KB |
testcase_60 | AC | 27 ms
11,520 KB |
testcase_61 | AC | 28 ms
11,520 KB |
testcase_62 | AC | 27 ms
11,520 KB |
testcase_63 | AC | 28 ms
11,392 KB |
testcase_64 | AC | 27 ms
11,520 KB |
testcase_65 | AC | 28 ms
11,520 KB |
testcase_66 | AC | 26 ms
11,392 KB |
testcase_67 | AC | 26 ms
11,520 KB |
testcase_68 | AC | 27 ms
11,520 KB |
testcase_69 | AC | 27 ms
11,392 KB |
testcase_70 | AC | 28 ms
11,392 KB |
testcase_71 | AC | 27 ms
11,520 KB |
testcase_72 | AC | 28 ms
11,520 KB |
testcase_73 | AC | 27 ms
11,392 KB |
testcase_74 | AC | 27 ms
11,520 KB |
testcase_75 | AC | 27 ms
11,392 KB |
testcase_76 | AC | 27 ms
11,520 KB |
testcase_77 | AC | 26 ms
11,392 KB |
testcase_78 | AC | 28 ms
11,520 KB |
testcase_79 | AC | 28 ms
11,392 KB |
testcase_80 | AC | 27 ms
11,520 KB |
testcase_81 | AC | 27 ms
11,392 KB |
testcase_82 | AC | 27 ms
11,392 KB |
testcase_83 | AC | 27 ms
11,520 KB |
testcase_84 | AC | 26 ms
11,520 KB |
testcase_85 | AC | 26 ms
11,520 KB |
testcase_86 | AC | 26 ms
11,520 KB |
testcase_87 | AC | 27 ms
11,392 KB |
testcase_88 | AC | 27 ms
11,392 KB |
testcase_89 | AC | 27 ms
11,392 KB |
testcase_90 | AC | 26 ms
11,520 KB |
testcase_91 | AC | 27 ms
11,520 KB |
testcase_92 | AC | 26 ms
11,520 KB |
testcase_93 | AC | 27 ms
11,520 KB |
testcase_94 | AC | 27 ms
11,520 KB |
testcase_95 | AC | 28 ms
11,392 KB |
testcase_96 | AC | 26 ms
11,520 KB |
testcase_97 | AC | 28 ms
11,392 KB |
testcase_98 | AC | 30 ms
11,520 KB |
testcase_99 | AC | 29 ms
11,520 KB |
testcase_100 | AC | 29 ms
11,392 KB |
testcase_101 | AC | 27 ms
11,392 KB |
testcase_102 | AC | 28 ms
11,520 KB |
testcase_103 | AC | 27 ms
11,392 KB |
testcase_104 | AC | 28 ms
11,392 KB |
testcase_105 | AC | 27 ms
11,392 KB |
testcase_106 | AC | 28 ms
11,520 KB |
testcase_107 | AC | 27 ms
11,392 KB |
testcase_108 | AC | 27 ms
11,520 KB |
testcase_109 | AC | 27 ms
11,520 KB |
testcase_110 | AC | 27 ms
11,520 KB |
testcase_111 | AC | 27 ms
11,520 KB |
testcase_112 | AC | 26 ms
11,520 KB |
testcase_113 | AC | 26 ms
11,520 KB |
testcase_114 | AC | 28 ms
11,520 KB |
testcase_115 | AC | 26 ms
11,520 KB |
testcase_116 | AC | 28 ms
11,392 KB |
testcase_117 | AC | 27 ms
11,520 KB |
testcase_118 | AC | 27 ms
11,520 KB |
testcase_119 | AC | 28 ms
11,392 KB |
testcase_120 | AC | 27 ms
11,520 KB |
testcase_121 | AC | 27 ms
11,520 KB |
testcase_122 | AC | 27 ms
11,392 KB |
testcase_123 | AC | 27 ms
11,392 KB |
testcase_124 | AC | 26 ms
11,392 KB |
testcase_125 | AC | 34 ms
11,520 KB |
testcase_126 | AC | 34 ms
11,520 KB |
testcase_127 | AC | 26 ms
11,392 KB |
testcase_128 | AC | 375 ms
18,236 KB |
testcase_129 | AC | 1,041 ms
29,100 KB |
testcase_130 | AC | 698 ms
23,584 KB |
testcase_131 | AC | 1,178 ms
32,992 KB |
testcase_132 | AC | 895 ms
32,544 KB |
testcase_133 | AC | 39 ms
11,520 KB |
testcase_134 | AC | 97 ms
18,172 KB |
testcase_135 | AC | 271 ms
19,048 KB |
testcase_136 | AC | 302 ms
18,348 KB |
testcase_137 | AC | 169 ms
22,932 KB |
testcase_138 | AC | 651 ms
26,308 KB |
testcase_139 | AC | 770 ms
28,560 KB |
testcase_140 | AC | 276 ms
35,380 KB |
testcase_141 | AC | 922 ms
33,708 KB |
testcase_142 | AC | 391 ms
20,680 KB |
testcase_143 | AC | 199 ms
25,892 KB |
testcase_144 | AC | 1,094 ms
31,080 KB |
testcase_145 | AC | 90 ms
12,544 KB |
testcase_146 | AC | 213 ms
16,120 KB |
testcase_147 | AC | 811 ms
26,684 KB |
testcase_148 | AC | 165 ms
19,624 KB |
testcase_149 | AC | 245 ms
24,656 KB |
testcase_150 | AC | 340 ms
30,508 KB |
testcase_151 | AC | 44 ms
12,416 KB |
testcase_152 | AC | 272 ms
28,072 KB |
testcase_153 | AC | 321 ms
35,488 KB |
testcase_154 | AC | 48 ms
11,904 KB |
testcase_155 | AC | 570 ms
28,296 KB |
testcase_156 | AC | 205 ms
16,944 KB |
testcase_157 | AC | 581 ms
28,692 KB |
testcase_158 | AC | 600 ms
34,700 KB |
testcase_159 | AC | 117 ms
14,836 KB |
testcase_160 | AC | 55 ms
12,160 KB |
testcase_161 | AC | 653 ms
31,208 KB |
testcase_162 | AC | 254 ms
32,516 KB |
testcase_163 | AC | 185 ms
23,072 KB |
testcase_164 | AC | 401 ms
34,024 KB |
testcase_165 | AC | 327 ms
28,908 KB |
testcase_166 | AC | 77 ms
14,716 KB |
testcase_167 | AC | 206 ms
22,508 KB |
testcase_168 | AC | 260 ms
19,252 KB |
testcase_169 | AC | 295 ms
20,044 KB |
testcase_170 | AC | 232 ms
18,328 KB |
testcase_171 | AC | 398 ms
22,908 KB |
testcase_172 | AC | 174 ms
20,364 KB |
testcase_173 | AC | 53 ms
12,928 KB |
testcase_174 | AC | 346 ms
31,160 KB |
testcase_175 | AC | 416 ms
35,620 KB |
testcase_176 | AC | 300 ms
27,532 KB |
testcase_177 | AC | 60 ms
13,556 KB |
testcase_178 | AC | 307 ms
28,304 KB |
testcase_179 | AC | 326 ms
29,504 KB |
testcase_180 | AC | 306 ms
32,468 KB |
testcase_181 | AC | 83 ms
16,096 KB |
testcase_182 | AC | 146 ms
20,776 KB |
testcase_183 | AC | 212 ms
25,208 KB |
testcase_184 | AC | 168 ms
21,512 KB |
testcase_185 | AC | 224 ms
27,088 KB |
testcase_186 | AC | 275 ms
31,268 KB |
testcase_187 | AC | 209 ms
26,084 KB |
testcase_188 | AC | 28 ms
11,520 KB |
testcase_189 | AC | 27 ms
11,520 KB |
testcase_190 | AC | 27 ms
11,520 KB |
testcase_191 | AC | 26 ms
11,392 KB |
testcase_192 | AC | 27 ms
11,520 KB |
testcase_193 | AC | 26 ms
11,392 KB |
testcase_194 | AC | 27 ms
11,392 KB |
testcase_195 | AC | 26 ms
11,520 KB |
testcase_196 | AC | 832 ms
26,112 KB |
testcase_197 | AC | 241 ms
15,460 KB |
testcase_198 | AC | 636 ms
22,200 KB |
testcase_199 | AC | 891 ms
27,196 KB |
testcase_200 | AC | 538 ms
30,364 KB |
testcase_201 | AC | 374 ms
21,832 KB |
testcase_202 | AC | 1,014 ms
29,052 KB |
testcase_203 | AC | 567 ms
20,804 KB |
testcase_204 | AC | 1,275 ms
33,740 KB |
testcase_205 | AC | 617 ms
21,948 KB |
testcase_206 | AC | 413 ms
33,420 KB |
testcase_207 | AC | 701 ms
27,552 KB |
testcase_208 | AC | 943 ms
27,452 KB |
testcase_209 | AC | 309 ms
16,192 KB |
testcase_210 | AC | 151 ms
13,684 KB |
testcase_211 | AC | 441 ms
19,448 KB |
testcase_212 | AC | 135 ms
16,236 KB |
testcase_213 | AC | 463 ms
22,408 KB |
testcase_214 | AC | 1,323 ms
34,768 KB |
testcase_215 | AC | 1,064 ms
30,300 KB |
testcase_216 | AC | 1,260 ms
33,320 KB |
testcase_217 | AC | 675 ms
23,212 KB |
testcase_218 | AC | 556 ms
34,188 KB |
testcase_219 | AC | 235 ms
22,920 KB |
ソースコード
import sys from collections import namedtuple read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines INF = 10**10 Segment = namedtuple('Segment', ('x', 'y', 'dx', 'dy', 'n')) Rectangle = namedtuple('Rectangle', ('x1', 'y1', 'x2', 'y2')) Pt = namedtuple('Pt', ('x', 'y')) W, H = map(int, readline().split()) N = int(readline()) m = map(int, read().split()) X,Y = zip(*zip(m,m)) x0, y0 = X[0], Y[0] def solve_two(x0, y0, x, y): if x0 > x: x0, x = x, x0 y0, y = y, y0 dx = x - x0 dy = y - y0 if (dx + dy) % 2 != 0: return if dx == abs(dy): if dy > 0: yield Rectangle(-INF, y, x0, INF) yield Rectangle(x, -INF, INF, y0) if dx > 1: yield Segment(x0 + 1, y - 1, 1, -1, dx - 2) else: yield Rectangle(-INF, -INF, x0, y) yield Rectangle(x, y0, INF, INF) if dx > 1: yield Segment(x0 + 1, y + 1, 1, 1, dx - 2) return d = (dx + abs(dy)) // 2 if dx == 0: y = (y + y0) // 2 yield Segment(-INF, y, 1, 0, INF * 2) elif dy == 0: x = (x + x0) // 2 yield Segment(x, -INF, 0, 1, INF * 2) elif dx < dy: yield Segment(x0,y0+d,-1,0,INF) yield Segment(x, y-d, 1, 0, INF) if dx > 1: yield Segment(x0+1,y0+d-1,1,-1,dx-2) elif 0 < dy < dx: yield Segment(x-d,y,0,1,INF) if dy > 1: yield Segment(x - d + 1, y - 1, 1, -1, dy - 2) yield Segment(x0 + d, y0, 0, -1, INF) elif 0 < dx < -dy: yield Segment(x0, y0-d, -1, 0, INF) if dx > 1: yield Segment(x0+1,y0-d+1,1,1,dx - 2) yield Segment(x, y + d, 1, 0, INF) elif 0 < -dy < dx: yield Segment(x0+d,y0, 0, 1, INF) if -dy > 1: yield Segment(x-d+1,y+1, 1, 1, -dy - 2) yield Segment(x-d,y,0,-1,INF) else: raise Exception def modify(seg): x,y,dx,dy,n = seg if dx == -1: return Segment(x+dx*n,y+dy*n,-dx,-dy,n) if dx == 0 and dy == -1: return Segment(x,y-n,0,1,n) return seg def ptpt(pt1, pt2): if pt1.x == pt2.x and pt1.y == pt2.y: return pt1 else: return None def segpt(seg, pt): seg = modify(seg) d = abs(seg.x - pt.x) + abs(seg.y - pt.y) k = d // (abs(seg.dx) + abs(seg.dy)) if not (0 <= k <= seg.n): return None if seg.x + seg.dx * k == pt.x and seg.y + seg.dy * k == pt.y: return pt return None def recpt(rec, pt): if (rec.x1 <= pt.x <= rec.x2) and (rec.y1 <= pt.y <= rec.y2): return pt return None def recrec(rec1, rec2): x1 = max(rec1.x1, rec2.x1) x2 = min(rec1.x2, rec2.x2) y1 = max(rec1.y1, rec2.y1) y2 = min(rec1.y2, rec2.y2) if x1 <= x2 and y1 <= y2: return Rectangle(x1, y1, x2, y2) return None def recseg(rec, seg): seg = modify(seg) if seg.dx == 0: if not (rec.x1 <= seg.x <= rec.x2): return None low_x, high_x = 0, INF * 2 elif seg.dx == 1: low_x, high_x = rec.x1 - seg.x, rec.x2 - seg.x else: low_x, high_x = seg.x - rec.x2, seg.x - rec.x1 if seg.dy == 0: if not (rec.y1 <= seg.y <= rec.y2): return None low_y, high_y = 0, INF * 2 elif seg.dy == 1: low_y, high_y = rec.y1 - seg.y, rec.y2 - seg.y else: low_y, high_y = seg.y - rec.y2, seg.y - rec.y1 low = max(low_x, low_y, 0) high = min(high_x, high_y, seg.n) if low > high: return None return Segment(seg.x + seg.dx * low, seg.y + seg.dy * low, seg.dx, seg.dy, high - low) def segseg(seg1, seg2): seg1 = modify(seg1) seg2 = modify(seg2) x1, y1, a1, b1 = seg1.x, seg1.y, seg1.dx, seg1.dy x2, y2, a2, b2 = seg2.x, seg2.y, seg2.dx, seg2.dy det = -a1 * b2 + a2 * b1 if det != 0: x, y = x2 - x1, y2 - y1 s = (-b2 * x + a2 * y) // det t = (-b1 * x + a1 * y) // det if not ((0 <= s <= seg1.n) and (0 <= t <= seg2.n)): return None x, y = x1 + a1 * s, y1 + b1 * s if (x != x2 + a2 * t) or (y != y2 + b2 * t): return None return Pt(x, y) x1, y1, a1, b1 = seg1.x, seg1.y, seg1.dx, seg1.dy x2, y2, a2, b2 = seg2.x, seg2.y, seg2.dx, seg2.dy assert a1 == a2 and b1 == b2 a, b = a1, b1 if b * x1 - a * y1 != b * x2 - a * y2: # 交わらない平行線 return None # 直線として同じ if a == 1: low_x = max(x1, x2) high_x = min(x1 + seg1.n, x2 + seg2.n) if low_x > high_x: return None return Segment(low_x, y1 + b * (low_x - x1), a, b, high_x - low_x) assert a == 0 and b == 1 low_y = max(y1, y2) high_y = min(y1 + seg1.n, y2 + seg2.n) if low_y > high_y: return None return Segment(x1, low_y, 0, 1, high_y - low_y) def intersect_two(shape1, shape2): if isinstance(shape1, Rectangle): if isinstance(shape2, Rectangle): return recrec(shape1, shape2) if isinstance(shape2, Segment): return recseg(shape1, shape2) return recpt(shape1, shape2) if isinstance(shape1, Segment): if isinstance(shape2, Rectangle): return recseg(shape2, shape1) if isinstance(shape2, Segment): return segseg(shape1, shape2) return segpt(shape1, shape2) if isinstance(shape2, Rectangle): return recpt(shape2, shape1) if isinstance(shape2, Segment): return segpt(shape2, shape1) return ptpt(shape1, shape2) def intersect(pts1, pts2): for shape1 in pts1: for shape2 in pts2: shape = intersect_two(shape1, shape2) if shape is None: continue yield shape def count_pt(shape): if isinstance(shape, Rectangle): return (shape.x2 - shape.x1 + 1) * (shape.y2 - shape.y1 + 1) if isinstance(shape, Segment): return shape.n + 1 return 1 pts = [Rectangle(1, 1, W, H)] for x, y in zip(X[1:], Y[1:]): pts1 = list(solve_two(x0, y0, x, y)) pts = list(intersect(pts, pts1)) answer = 0 for shape in pts: answer += count_pt(shape) print(answer)