結果
問題 | No.869 ふたつの距離 |
ユーザー |
![]() |
提出日時 | 2020-05-14 15:08:55 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 528 ms / 1,500 ms |
コード長 | 1,347 bytes |
コンパイル時間 | 160 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 44,676 KB |
最終ジャッジ日時 | 2024-09-15 07:23:16 |
合計ジャッジ時間 | 53,141 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 93 |
ソースコード
import sysimport numpy as npread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesdef solve_on_circ(N, A):A0 = An = (N + 1) // 2m = N - nA -= n * (n - 1) // 2 + m * (m - 1) // 2assert A >= 0x = np.linspace(0, 0.1, n + 1)[::-1]dx = 0.1 / (n + n)y = []phi = 2 * np.arcsin(0.25)for i in range(m):t = min(n, A)A -= ty.append(phi + x[t] + dx)t = np.concatenate([x[:-1], y])x = 20 * np.cos(t)y = 20 * np.sin(t)return x, ydef other_points(M):x = np.linspace(100, 90000, M)y = np.zeros_like(x)return x, ydef solve(N, A, B):left = 0 # B 未満right = N # B以上while left + 1 < right:x = (left + right) // 2if x * (x - 1) // 2 >= B:right = xelse:left = xn = rightx0, y0 = other_points(N - n)x, y = solve_on_circ(n - 1, A)far = n * (n - 1) // 2 - Beps = 1e-7x[:far] *= (1 + eps)y[:far] *= (1 + eps)x[far:] *= (1 - eps)y[far:] *= (1 - eps)x = np.concatenate([[0], x, x0])y = np.concatenate([[0], y, y0])return x, yN, A, B = map(int, read().split())x, y = solve(N, A, B)xy = np.vstack([x, y]).Tprint('\n'.join(' '.join(row) for row in xy.astype(str)))