結果
問題 | No.960 マンハッタン距離3 |
ユーザー |
![]() |
提出日時 | 2020-05-10 06:14:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 450 ms / 2,000 ms |
コード長 | 6,278 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 82,424 KB |
実行使用メモリ | 110,948 KB |
最終ジャッジ日時 | 2024-07-06 23:39:06 |
合計ジャッジ時間 | 29,517 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 216 |
ソースコード
import sysfrom collections import namedtupleread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesINF = 10**10Segment = 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, x0y0, y = y, y0dx = x - x0dy = y - y0if (dx + dy) % 2 != 0:returnif 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)returnd = (dx + abs(dy)) // 2if dx == 0:y = (y + y0) // 2yield Segment(-INF, y, 1, 0, INF * 2)elif dy == 0:x = (x + x0) // 2yield 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 Exceptiondef modify(seg):x,y,dx,dy,n = segif 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 segdef ptpt(pt1, pt2):if pt1.x == pt2.x and pt1.y == pt2.y:return pt1else:return Nonedef 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 Noneif seg.x + seg.dx * k == pt.x and seg.y + seg.dy * k == pt.y:return ptreturn Nonedef recpt(rec, pt):if (rec.x1 <= pt.x <= rec.x2) and (rec.y1 <= pt.y <= rec.y2):return ptreturn Nonedef 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 Nonedef recseg(rec, seg):seg = modify(seg)if seg.dx == 0:if not (rec.x1 <= seg.x <= rec.x2):return Nonelow_x, high_x = 0, INF * 2elif seg.dx == 1:low_x, high_x = rec.x1 - seg.x, rec.x2 - seg.xelse:low_x, high_x = seg.x - rec.x2, seg.x - rec.x1if seg.dy == 0:if not (rec.y1 <= seg.y <= rec.y2):return Nonelow_y, high_y = 0, INF * 2elif seg.dy == 1:low_y, high_y = rec.y1 - seg.y, rec.y2 - seg.yelse:low_y, high_y = seg.y - rec.y2, seg.y - rec.y1low = max(low_x, low_y, 0)high = min(high_x, high_y, seg.n)if low > high:return Nonereturn 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.dyx2, y2, a2, b2 = seg2.x, seg2.y, seg2.dx, seg2.dydet = -a1 * b2 + a2 * b1if det != 0:x, y = x2 - x1, y2 - y1s = (-b2 * x + a2 * y) // dett = (-b1 * x + a1 * y) // detif not ((0 <= s <= seg1.n) and (0 <= t <= seg2.n)):return Nonex, y = x1 + a1 * s, y1 + b1 * sif (x != x2 + a2 * t) or (y != y2 + b2 * t):return Nonereturn Pt(x, y)x1, y1, a1, b1 = seg1.x, seg1.y, seg1.dx, seg1.dyx2, y2, a2, b2 = seg2.x, seg2.y, seg2.dx, seg2.dyassert a1 == a2 and b1 == b2a, b = a1, b1if 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 Nonereturn Segment(low_x, y1 + b * (low_x - x1), a, b, high_x - low_x)assert a == 0 and b == 1low_y = max(y1, y2)high_y = min(y1 + seg1.n, y2 + seg2.n)if low_y > high_y:return Nonereturn 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:continueyield shapedef 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 + 1return 1pts = [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 = 0for shape in pts:answer += count_pt(shape)print(answer)