#479987 (PyPy3) No.960 マンハッタン距離3

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	maspy
提出日時	2020-05-10 06:14:44
言語	PyPy3 (7.3.15)
結果	AC
実行時間	501 ms / 2,000 ms
コード長	6,278 bytes
コンパイル時間	295 ms
コンパイル使用メモリ	87,112 KB
実行使用メモリ	116,288 KB
最終ジャッジ日時	2023-09-21 05:07:04
合計ジャッジ時間	43,817 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	98 ms 72,204 KB
testcase_01	AC	99 ms 71,908 KB
testcase_02	AC	98 ms 71,928 KB
testcase_03	AC	98 ms 71,976 KB
testcase_04	AC	97 ms 72,044 KB
testcase_05	AC	95 ms 72,036 KB
testcase_06	AC	98 ms 71,996 KB
testcase_07	AC	97 ms 71,952 KB
testcase_08	AC	98 ms 72,152 KB
testcase_09	AC	98 ms 71,960 KB
testcase_10	AC	98 ms 72,032 KB
testcase_11	AC	98 ms 71,996 KB
testcase_12	AC	98 ms 72,088 KB
testcase_13	AC	95 ms 71,964 KB
testcase_14	AC	96 ms 72,160 KB
testcase_15	AC	95 ms 72,116 KB
testcase_16	AC	96 ms 72,068 KB
testcase_17	AC	96 ms 72,180 KB
testcase_18	AC	96 ms 71,932 KB
testcase_19	AC	98 ms 72,100 KB
testcase_20	AC	114 ms 76,156 KB
testcase_21	AC	106 ms 76,216 KB
testcase_22	AC	98 ms 72,208 KB
testcase_23	AC	98 ms 71,908 KB
testcase_24	AC	99 ms 72,252 KB
testcase_25	AC	99 ms 72,192 KB
testcase_26	AC	98 ms 72,184 KB
testcase_27	AC	103 ms 75,880 KB
testcase_28	AC	101 ms 76,028 KB
testcase_29	AC	97 ms 72,252 KB
testcase_30	AC	103 ms 75,836 KB
testcase_31	AC	101 ms 75,820 KB
testcase_32	AC	96 ms 72,104 KB
testcase_33	AC	104 ms 76,060 KB
testcase_34	AC	104 ms 75,892 KB
testcase_35	AC	98 ms 72,016 KB
testcase_36	AC	106 ms 75,812 KB
testcase_37	AC	97 ms 71,780 KB
testcase_38	AC	100 ms 75,888 KB
testcase_39	AC	100 ms 75,824 KB
testcase_40	AC	99 ms 71,928 KB
testcase_41	AC	95 ms 72,016 KB
testcase_42	AC	97 ms 72,028 KB
testcase_43	AC	99 ms 71,952 KB
testcase_44	AC	98 ms 71,912 KB
testcase_45	AC	97 ms 72,096 KB
testcase_46	AC	102 ms 75,960 KB
testcase_47	AC	98 ms 72,060 KB
testcase_48	AC	103 ms 76,052 KB
testcase_49	AC	105 ms 75,888 KB
testcase_50	AC	101 ms 76,124 KB
testcase_51	AC	99 ms 71,976 KB
testcase_52	AC	99 ms 72,180 KB
testcase_53	AC	104 ms 75,900 KB
testcase_54	AC	99 ms 71,908 KB
testcase_55	AC	99 ms 72,152 KB
testcase_56	AC	99 ms 72,016 KB
testcase_57	AC	97 ms 72,152 KB
testcase_58	AC	99 ms 72,204 KB
testcase_59	AC	97 ms 72,016 KB
testcase_60	AC	104 ms 75,900 KB
testcase_61	AC	103 ms 76,060 KB
testcase_62	AC	105 ms 75,984 KB
testcase_63	AC	105 ms 75,932 KB
testcase_64	AC	99 ms 72,076 KB
testcase_65	AC	98 ms 72,316 KB
testcase_66	AC	98 ms 72,020 KB
testcase_67	AC	98 ms 72,152 KB
testcase_68	AC	98 ms 71,772 KB
testcase_69	AC	99 ms 71,904 KB
testcase_70	AC	97 ms 71,908 KB
testcase_71	AC	100 ms 72,232 KB
testcase_72	AC	109 ms 76,812 KB
testcase_73	AC	108 ms 76,516 KB
testcase_74	AC	99 ms 72,216 KB
testcase_75	AC	98 ms 72,016 KB
testcase_76	AC	99 ms 71,796 KB
testcase_77	AC	98 ms 71,984 KB
testcase_78	AC	99 ms 72,008 KB
testcase_79	AC	100 ms 72,028 KB
testcase_80	AC	98 ms 71,940 KB
testcase_81	AC	98 ms 72,012 KB
testcase_82	AC	97 ms 72,276 KB
testcase_83	AC	97 ms 72,084 KB
testcase_84	AC	96 ms 71,972 KB
testcase_85	AC	96 ms 72,012 KB
testcase_86	AC	97 ms 71,968 KB
testcase_87	AC	96 ms 71,972 KB
testcase_88	AC	98 ms 71,936 KB
testcase_89	AC	101 ms 75,992 KB
testcase_90	AC	99 ms 72,128 KB
testcase_91	AC	99 ms 72,188 KB
testcase_92	AC	96 ms 71,808 KB
testcase_93	AC	95 ms 71,796 KB
testcase_94	AC	99 ms 75,992 KB
testcase_95	AC	101 ms 75,932 KB
testcase_96	AC	100 ms 76,128 KB
testcase_97	AC	101 ms 76,196 KB
testcase_98	AC	98 ms 72,064 KB
testcase_99	AC	99 ms 72,128 KB
testcase_100	AC	102 ms 75,940 KB
testcase_101	AC	101 ms 75,860 KB
testcase_102	AC	103 ms 76,128 KB
testcase_103	AC	99 ms 72,040 KB
testcase_104	AC	96 ms 72,204 KB
testcase_105	AC	96 ms 72,100 KB
testcase_106	AC	97 ms 72,172 KB
testcase_107	AC	100 ms 72,188 KB
testcase_108	AC	97 ms 72,384 KB
testcase_109	AC	102 ms 76,096 KB
testcase_110	AC	100 ms 72,084 KB
testcase_111	AC	97 ms 72,016 KB
testcase_112	AC	97 ms 72,308 KB
testcase_113	AC	98 ms 72,080 KB
testcase_114	AC	98 ms 72,212 KB
testcase_115	AC	98 ms 71,948 KB
testcase_116	AC	98 ms 72,332 KB
testcase_117	AC	97 ms 72,312 KB
testcase_118	AC	98 ms 72,056 KB
testcase_119	AC	97 ms 72,256 KB
testcase_120	AC	97 ms 71,988 KB
testcase_121	AC	98 ms 72,220 KB
testcase_122	AC	98 ms 71,928 KB
testcase_123	AC	99 ms 72,280 KB
testcase_124	AC	97 ms 72,220 KB
testcase_125	AC	95 ms 72,060 KB
testcase_126	AC	96 ms 72,136 KB
testcase_127	AC	97 ms 72,056 KB
testcase_128	AC	247 ms 85,224 KB
testcase_129	AC	299 ms 103,376 KB
testcase_130	AC	273 ms 93,684 KB
testcase_131	AC	326 ms 108,268 KB
testcase_132	AC	339 ms 107,652 KB
testcase_133	AC	172 ms 79,292 KB
testcase_134	AC	142 ms 84,296 KB
testcase_135	AC	228 ms 86,596 KB
testcase_136	AC	241 ms 85,416 KB
testcase_137	AC	168 ms 93,752 KB
testcase_138	AC	297 ms 97,860 KB
testcase_139	AC	303 ms 101,280 KB
testcase_140	AC	219 ms 116,160 KB
testcase_141	AC	338 ms 109,548 KB
testcase_142	AC	237 ms 89,200 KB
testcase_143	AC	174 ms 98,500 KB
testcase_144	AC	501 ms 105,000 KB
testcase_145	AC	365 ms 83,664 KB
testcase_146	AC	203 ms 83,076 KB
testcase_147	AC	446 ms 98,240 KB
testcase_148	AC	208 ms 88,324 KB
testcase_149	AC	189 ms 95,788 KB
testcase_150	AC	211 ms 104,916 KB
testcase_151	AC	136 ms 77,984 KB
testcase_152	AC	180 ms 100,928 KB
testcase_153	AC	224 ms 115,836 KB
testcase_154	AC	242 ms 79,980 KB
testcase_155	AC	363 ms 101,096 KB
testcase_156	AC	308 ms 83,860 KB
testcase_157	AC	351 ms 100,612 KB
testcase_158	AC	327 ms 116,288 KB
testcase_159	AC	234 ms 80,976 KB
testcase_160	AC	219 ms 79,296 KB
testcase_161	AC	388 ms 104,908 KB
testcase_162	AC	198 ms 107,884 KB
testcase_163	AC	187 ms 93,740 KB
testcase_164	AC	229 ms 111,184 KB
testcase_165	AC	240 ms 102,324 KB
testcase_166	AC	159 ms 80,652 KB
testcase_167	AC	193 ms 93,132 KB
testcase_168	AC	382 ms 86,804 KB
testcase_169	AC	380 ms 88,036 KB
testcase_170	AC	353 ms 85,460 KB
testcase_171	AC	406 ms 93,864 KB
testcase_172	AC	170 ms 89,484 KB
testcase_173	AC	152 ms 78,408 KB
testcase_174	AC	252 ms 105,776 KB
testcase_175	AC	276 ms 116,124 KB
testcase_176	AC	212 ms 101,260 KB
testcase_177	AC	158 ms 79,448 KB
testcase_178	AC	230 ms 101,224 KB
testcase_179	AC	233 ms 104,040 KB
testcase_180	AC	247 ms 108,356 KB
testcase_181	AC	175 ms 82,892 KB
testcase_182	AC	193 ms 90,072 KB
testcase_183	AC	190 ms 96,220 KB
testcase_184	AC	187 ms 91,556 KB
testcase_185	AC	217 ms 99,612 KB
testcase_186	AC	231 ms 105,580 KB
testcase_187	AC	229 ms 98,368 KB
testcase_188	AC	97 ms 72,040 KB
testcase_189	AC	96 ms 72,196 KB
testcase_190	AC	97 ms 72,104 KB
testcase_191	AC	96 ms 72,080 KB
testcase_192	AC	96 ms 72,104 KB
testcase_193	AC	97 ms 72,172 KB
testcase_194	AC	97 ms 72,012 KB
testcase_195	AC	98 ms 71,996 KB
testcase_196	AC	335 ms 97,608 KB
testcase_197	AC	263 ms 81,504 KB
testcase_198	AC	300 ms 92,020 KB
testcase_199	AC	333 ms 100,440 KB
testcase_200	AC	280 ms 104,520 KB
testcase_201	AC	237 ms 92,012 KB
testcase_202	AC	336 ms 103,416 KB
testcase_203	AC	302 ms 89,572 KB
testcase_204	AC	377 ms 109,512 KB
testcase_205	AC	299 ms 92,224 KB
testcase_206	AC	272 ms 108,052 KB
testcase_207	AC	277 ms 100,704 KB
testcase_208	AC	323 ms 100,896 KB
testcase_209	AC	236 ms 83,612 KB
testcase_210	AC	194 ms 79,452 KB
testcase_211	AC	281 ms 86,392 KB
testcase_212	AC	217 ms 83,584 KB
testcase_213	AC	261 ms 92,200 KB
testcase_214	AC	403 ms 116,220 KB
testcase_215	AC	346 ms 104,400 KB
testcase_216	AC	377 ms 108,312 KB
testcase_217	AC	310 ms 93,956 KB
testcase_218	AC	297 ms 111,148 KB
testcase_219	AC	251 ms 93,324 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)

yukicoder

結果

テストケース

ソースコード