結果

問題 No.960 マンハッタン距離3
ユーザー maspy
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0