結果
問題 | No.2632 Center of Three Points in Lp Norm |
ユーザー |
![]() |
提出日時 | 2024-02-16 22:38:46 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 1,628 bytes |
コンパイル時間 | 409 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 44,348 KB |
最終ジャッジ日時 | 2024-09-28 21:15:03 |
合計ジャッジ時間 | 24,704 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
import numpy as npfrom math import pi, cos, sin, atan2import sysZERO = np.array([0.0, 0.0])get = lambda: np.array(list(map(float, input().split())))def norm(a) -> float:x = abs(a[0])y = abs(a[1])if x > y:x, y = y, xif y == 0.0:return 0.0x /= yreturn pow(1.0 + pow(x, p), 1 / p) * ydef dist(a, b):return norm(a - b)def cross(a, b):return a[0] * b[1] - a[1] * b[0]p = float(input())a = get()b = get()c = get()if a[0] > b[0]:a, b = b, aif a[0] > c[0]:a, c = c, aif cross(b - a, c - a) < 0:b, c = c, bA = a.copy()a -= Ab -= Ac -= AB = -piC = pidef atan(diff) -> float:return atan2(diff[1], diff[0])def near(diff) -> int:da = dist(a, diff)db = dist(b, diff)dc = dist(c, diff)mn = min(da, db, dc)if da == mn: return 0if db == mn: return 1return 2def bisect_a(di):ok = 1e7ng = 0.0for _ in range(100):mid = (ok + ng) / 2if near(di * mid) == 0:ng = midelse:ok = midreturn di * okdef direction(theta):return np.array([cos(theta), sin(theta)])def check(theta):di = direction(theta)x = bisect_a(di)n = near(x)if n:return nif theta < atan(b):return 1return 2for _ in range(100):theta = (B + C) / 2if check(theta) == 1:B = thetaelse:C = thetaans = bisect_a(direction(B))if max(abs(ans[0]), abs(ans[1])) > 1e6:ans = bisect_a(direction(C))print(dist(a, ans), dist(b, ans), dist(c, ans), file=sys.stderr)print(*(ans + A))