結果

問題 No.168 ものさし
ユーザー 👑 obakyan
提出日時 2020-04-23 21:57:56
言語 Lua
(LuaJit 2.1.1734355927)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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