結果
問題 |
No.168 ものさし
|
ユーザー |
|
提出日時 | 2022-04-17 09:37:37 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 499 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 135,584 KB |
最終ジャッジ日時 | 2024-12-26 04:58:12 |
合計ジャッジ時間 | 31,116 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 18 TLE * 1 |
ソースコード
import numpy as np from scipy.sparse.csgraph import connected_components N = int(input()) P = np.array([tuple(map(int, input().split())) for _ in range(N)],dtype=np.int64) X, Y = P[:, 0], P[:, 1] D = (X[:, None] - X[None, :]) ** 2 + (Y[:, None] - Y[None, :]) ** 2 def f(x): _, labels = connected_components(D <= x ** 2) return labels[0] == labels[-1] # bisect l, r = 0, 2 * 10 ** 9 while r - l > 10: m = (r + l) // 20 * 10 if f(m): r = m else: l = m print(r)