#491090 (Python3) No.131 マンハッタン距離

提出ソース

結果

問題	No.131 マンハッタン距離
ユーザー	Coki628
提出日時	2020-06-03 01:39:21
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	21 ms / 5,000 ms
コード長	6,632 bytes
コンパイル時間	115 ms
コンパイル使用メモリ	11,844 KB
実行使用メモリ	9,368 KB
最終ジャッジ日時	2023-08-16 11:02:19
合計ジャッジ時間	1,850 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	19 ms 9,276 KB
testcase_01	AC	19 ms 9,232 KB
testcase_02	AC	19 ms 9,324 KB
testcase_03	AC	21 ms 9,276 KB
testcase_04	AC	20 ms 9,220 KB
testcase_05	AC	19 ms 9,232 KB
testcase_06	AC	19 ms 9,264 KB
testcase_07	AC	19 ms 9,212 KB
testcase_08	AC	19 ms 9,176 KB
testcase_09	AC	19 ms 9,228 KB
testcase_10	AC	19 ms 9,236 KB
testcase_11	AC	19 ms 9,352 KB
testcase_12	AC	19 ms 9,140 KB
testcase_13	AC	18 ms 9,272 KB
testcase_14	AC	19 ms 9,276 KB
testcase_15	AC	19 ms 9,212 KB
testcase_16	AC	19 ms 9,304 KB
testcase_17	AC	19 ms 9,136 KB
testcase_18	AC	19 ms 9,268 KB
testcase_19	AC	19 ms 9,368 KB
testcase_20	AC	19 ms 9,196 KB
testcase_21	AC	19 ms 9,200 KB
testcase_22	AC	19 ms 9,224 KB
testcase_23	AC	19 ms 9,324 KB
testcase_24	AC	19 ms 9,368 KB
testcase_25	AC	19 ms 9,280 KB
testcase_26	AC	19 ms 9,316 KB

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

ソースコード

raw source code

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class Geometry:
    """ 幾何学計算用クラス """

    def __init__(self, EPS):
        self.EPS = EPS

    def add(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1+x2, y1+y2)

    def sub(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1-x2, y1-y2)

    def mul(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1*b, y1*b)
        x2, y2 = b 
        return (x1*x2, y1*y2)

    def div(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1/b, y1/b)
        x2, y2 = b
        return (x1/x2, y1/y2)

    def abs(self, a):
        from math import hypot
        x1, y1 = a
        return hypot(x1, y1)

    def norm(self, a):
        x, y = a
        return x**2 + y**2

    def dot(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*x2 + y1*y2

    def cross(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*y2 - y1*x2

    def project(self, seg, p):
        """ 線分segに対する点pの射影 """

        p1, p2 = seg
        base = self.sub(p2, p1)
        r = self.dot(self.sub(p, p1), base) / self.norm(base)
        return self.add(p1, self.mul(base, r))

    def reflect(self, seg, p):
        """ 線分segを対称軸とした点pの線対称の点 """

        return self.add(p, self.mul(self.sub(self.project(seg, p), p), 2))

    def ccw(self, p0, p1, p2):
        """ 線分p0,p1から線分p0,p2への回転方向 """

        a = self.sub(p1, p0)
        b = self.sub(p2, p0)
        # 反時計回り
        if self.cross(a, b) > self.EPS: return 1
        # 時計回り
        if self.cross(a, b) < -self.EPS: return -1
        # 直線上(p2 => p0 => p1)
        if self.dot(a, b) < -self.EPS: return 2
        # 直線上(p0 => p1 => p2)
        if self.norm(a) < self.norm(b): return -2
        # 直線上(p0 => p2 => p1)
        return 0

    def intersect(self, seg1, seg2):
        """ 線分seg1と線分seg2の交差判定 """

        p1, p2 = seg1
        p3, p4 = seg2
        return (
            self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0
            and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0
        )

    def get_distance_PP(self, p1, p2):
        from math import hypot

        x1, y1 = p1
        x2, y2 = p2
        return hypot(x1-x2, y1-y2)

    def get_distance_LP(self, line, p):
        """ 直線lineと点pの距離 """

        p1, p2 = line
        return abs(self.cross(self.sub(p2, p1), self.sub(p, p1)) / self.abs(self.sub(p2, p1)))

    def get_distance_SP(self, seg, p):
        """ 線分segと点pの距離 """

        p1, p2 = seg
        if self.dot(self.sub(p2, p1), self.sub(p, p1)) < 0: return self.abs(self.sub(p, p1))
        if self.dot(self.sub(p1, p2), self.sub(p, p2)) < 0: return self.abs(self.sub(p, p2))
        return self.get_distance_LP(seg, p)

    def get_distance_SS(self, seg1, seg2):
        """ 線分seg1と線分seg2の距離 """

        p1, p2 = seg1
        p3, p4 = seg2
        if self.intersect(seg1, seg2): return 0
        return min(
            self.get_distance_SP(seg1, p3), self.get_distance_SP(seg1, p4),
            self.get_distance_SP(seg2, p1), self.get_distance_SP(seg2, p2),
        )

    def get_cross_pointSS(self, seg1, seg2):
        """ 線分seg1と線分seg2の交点 """

        p1, p2 = seg1
        p3, p4 = seg2
        if not self.intersect(seg1, seg2): return (INF, INF)
        if p1 == p2: return p1
        if p3 == p4: return p3
        base = self.sub(p4, p3)
        dist1 = abs(self.cross(base, self.sub(p1, p3)))
        dist2 = abs(self.cross(base, self.sub(p2, p3)))
        t = dist1 / (dist1+dist2)
        return self.add(p1, self.mul(self.sub(p2, p1), t))

    def intersectCL(self, c, line):
        """ 円cと直線lineの交差判定 """

        x, y, r = c
        return self.get_distance_SP(line, (x, y)) <= r

    def get_cross_pointCL(self, c, line):
        """ 円cと直線lineの交点 """
        from math import sqrt

        if not self.intersectCL(c, line): return -1
        x, y, r = c
        p1, p2 = line
        pr = self.project(line, (x, y))
        e = self.div(self.sub(p2, p1), self.abs(self.sub(p2, p1)))
        base = sqrt(r*r - self.norm(self.sub(pr, (x, y))))
        return [self.add(pr, self.mul(e, base)), self.sub(pr, self.mul(e, base))]

    def arg(self, p):
        from math import atan2
        x, y = p
        return atan2(y, x)

    def polar(self, a, r):
        from math import sin, cos
        return (cos(r)*a, sin(r)*a)

    def intersectCC(self, c1, c2):
        """ 円c1と円c2の交差判定 """
        from math import hypot

        x1, y1, r1 = c1
        x2, y2, r2 = c2
        return hypot(x1-x2, y1-y2) <= r1 + r2
    
    def get_cross_pointCC(self, c1, c2):
        """ 円c1と円c2の交点 """
        from math import acos

        if not self.intersectCC(c1, c2): return -1
        x1, y1, r1 = c1
        x2, y2, r2 = c2
        try:
            d = self.abs(self.sub((x1, y1), (x2, y2)))
            a = acos((r1*r1+d*d-r2*r2) / (2*r1*d))
            t = self.arg(self.sub((x2, y2), (x1, y1)))
            return [self.add((x1, y1), self.polar(r1, t+a)), self.add((x1, y1), self.polar(r1, t-a))]
        except:
            # 一方が他方を内包しちゃってる場合等はここに飛ぶ(はず)
            return -1

x, y, d = MAP()

gm = Geometry(EPS)
a = gm.get_cross_pointSS(((0, d), (d, 0)), ((0, 0), (x, 0)))
b = gm.get_cross_pointSS(((0, d), (d, 0)), ((0, 0), (0, y)))
c = gm.get_cross_pointSS(((0, d), (d, 0)), ((0, y), (x, y)))
d = gm.get_cross_pointSS(((0, d), (d, 0)), ((x, 0), (x, y)))
li = []
for p in [a, b, c, d]:
    if p != (INF, INF) and p not in li:
        li.append(p)
if len(li) == 0:
    print(0)
    exit()
if len(li) == 1:
    print(1)
    exit()
p1, p2 = li
dist = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
ans = int(dist // 2 + 1)
print(ans)

yukicoder

結果

テストケース

ソースコード