結果
問題 | No.131 マンハッタン距離 |
ユーザー |
![]() |
提出日時 | 2020-06-03 01:39:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 35 ms / 5,000 ms |
コード長 | 6,632 bytes |
コンパイル時間 | 130 ms |
コンパイル使用メモリ | 13,696 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-11-24 23:19:03 |
合計ジャッジ時間 | 1,974 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
import sysdef 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 ** 19MOD = 10 ** 9 + 7EPS = 10 ** -10class Geometry:""" 幾何学計算用クラス """def __init__(self, EPS):self.EPS = EPSdef add(self, a, b):x1, y1 = ax2, y2 = breturn (x1+x2, y1+y2)def sub(self, a, b):x1, y1 = ax2, y2 = breturn (x1-x2, y1-y2)def mul(self, a, b):x1, y1 = aif not isinstance(b, tuple):return (x1*b, y1*b)x2, y2 = breturn (x1*x2, y1*y2)def div(self, a, b):x1, y1 = aif not isinstance(b, tuple):return (x1/b, y1/b)x2, y2 = breturn (x1/x2, y1/y2)def abs(self, a):from math import hypotx1, y1 = areturn hypot(x1, y1)def norm(self, a):x, y = areturn x**2 + y**2def dot(self, a, b):x1, y1 = ax2, y2 = breturn x1*x2 + y1*y2def cross(self, a, b):x1, y1 = ax2, y2 = breturn x1*y2 - y1*x2def project(self, seg, p):""" 線分segに対する点pの射影 """p1, p2 = segbase = 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 0def intersect(self, seg1, seg2):""" 線分seg1と線分seg2の交差判定 """p1, p2 = seg1p3, p4 = seg2return (self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0)def get_distance_PP(self, p1, p2):from math import hypotx1, y1 = p1x2, y2 = p2return hypot(x1-x2, y1-y2)def get_distance_LP(self, line, p):""" 直線lineと点pの距離 """p1, p2 = linereturn 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 = segif 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 = seg1p3, p4 = seg2if self.intersect(seg1, seg2): return 0return 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 = seg1p3, p4 = seg2if not self.intersect(seg1, seg2): return (INF, INF)if p1 == p2: return p1if p3 == p4: return p3base = 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 = creturn self.get_distance_SP(line, (x, y)) <= rdef get_cross_pointCL(self, c, line):""" 円cと直線lineの交点 """from math import sqrtif not self.intersectCL(c, line): return -1x, y, r = cp1, p2 = linepr = 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 atan2x, y = preturn atan2(y, x)def polar(self, a, r):from math import sin, cosreturn (cos(r)*a, sin(r)*a)def intersectCC(self, c1, c2):""" 円c1と円c2の交差判定 """from math import hypotx1, y1, r1 = c1x2, y2, r2 = c2return hypot(x1-x2, y1-y2) <= r1 + r2def get_cross_pointCC(self, c1, c2):""" 円c1と円c2の交点 """from math import acosif not self.intersectCC(c1, c2): return -1x1, y1, r1 = c1x2, y2, r2 = c2try: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 -1x, 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 = lidist = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])ans = int(dist // 2 + 1)print(ans)