結果

問題 No.168 ものさし
ユーザー 👑 obakyanobakyan
提出日時 2020-04-23 21:57:56
言語 Lua
(LuaJit 2.1.1696795921)
結果
AC  
実行時間 859 ms / 2,000 ms
コード長 1,062 bytes
コンパイル時間 261 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 23,936 KB
最終ジャッジ日時 2024-10-14 00:38:05
合計ジャッジ時間 5,665 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 148 ms
7,552 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 1 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 5 ms
5,248 KB
testcase_10 AC 15 ms
5,248 KB
testcase_11 AC 138 ms
7,168 KB
testcase_12 AC 524 ms
17,920 KB
testcase_13 AC 859 ms
23,936 KB
testcase_14 AC 667 ms
23,808 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 4 ms
5,248 KB
testcase_17 AC 7 ms
5,248 KB
testcase_18 AC 14 ms
5,248 KB
testcase_19 AC 579 ms
22,912 KB
testcase_20 AC 315 ms
23,808 KB
testcase_21 AC 724 ms
23,808 KB
testcase_22 AC 407 ms
23,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

local bls, brs = bit.lshift, bit.rshift
local n = io.read("*n")
local x, y = {}, {}
for i = 1, n do
  x[i], y[i] = io.read("*n", "*n")
end
local edge = {}
for i = 1, n - 1 do
  edge[i] = {}
  for j = i + 1, n do
    edge[i][j - i] = 1LL * (x[i] - x[j]) * (x[i] - x[j]) + 1LL * (y[i] - y[j]) * (y[i] - y[j])
  end
end

local asked = {}
local function solve(z)
  z = 1LL * z * z
  for i = 1, n do
    asked[i] = false
  end
  asked[1] = true
  local tasks = {1}
  while 0 < #tasks do
    local src = tasks[#tasks]
    table.remove(tasks)
    for dst = 1, n do
      local ok = false
      if src < dst then
        ok = edge[src][dst - src] <= z
      elseif dst < src then
        ok = edge[dst][src - dst] <= z
      end
      if ok then
        if not asked[dst] then
          asked[dst] = true
          table.insert(tasks, dst)
        end
      end
    end
  end
  return asked[n]
end
local min, max = 0, 150000000
while 1 < max - min do
  local mid = brs(min + max, 1)
  if solve(mid * 10) then
    max = mid
  else
    min = mid
  end
end
print(max * 10)
0