結果

問題 No.168 ものさし
ユーザー snipsnipsnipsnipsnipsnip
提出日時 2015-03-28 16:03:11
言語 Ruby
(3.3.0)
結果
AC  
実行時間 711 ms / 2,000 ms
コード長 3,378 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 11,612 KB
実行使用メモリ 23,500 KB
最終ジャッジ日時 2023-08-25 20:54:18
合計ジャッジ時間 5,683 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 295 ms
17,212 KB
testcase_01 AC 83 ms
15,336 KB
testcase_02 AC 82 ms
15,448 KB
testcase_03 AC 81 ms
15,188 KB
testcase_04 AC 81 ms
15,192 KB
testcase_05 AC 84 ms
15,340 KB
testcase_06 AC 84 ms
15,316 KB
testcase_07 AC 83 ms
15,072 KB
testcase_08 AC 83 ms
15,188 KB
testcase_09 AC 87 ms
15,288 KB
testcase_10 AC 92 ms
15,444 KB
testcase_11 AC 204 ms
17,080 KB
testcase_12 AC 246 ms
20,880 KB
testcase_13 AC 290 ms
23,424 KB
testcase_14 AC 124 ms
23,500 KB
testcase_15 AC 82 ms
15,072 KB
testcase_16 AC 83 ms
15,436 KB
testcase_17 AC 91 ms
15,388 KB
testcase_18 AC 90 ms
15,896 KB
testcase_19 AC 219 ms
23,064 KB
testcase_20 AC 173 ms
23,496 KB
testcase_21 AC 711 ms
23,420 KB
testcase_22 AC 460 ms
23,492 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

require 'set'

Problem168 = Struct.new(:points) do
  def solve
    @distance_cache = []
    @grid = Grid.new(points)
    w = isqrt(squared_distance_by_index(0, points.size - 1)) / 10
    longest = ((w + 1) * 10) ** 2
    shortest = -1
    p 10 * (1..w + 1).bsearch {|d|
      len = d * 10
      sqlen = len ** 2
      next true if longest <= sqlen
      next false if sqlen < shortest
      if minmax = reach(len, sqlen)
        longest = minmax[1] if minmax[1] < longest
        shortest = minmax[0] if shortest < minmax[0]
        true
      else
        false
      end
    }
  end

  private

  def isqrt(x)
    (1..x).bsearch {|r| x <= r ** 2 }
  end

  def reach(len, sqlen)
    goal = points.size - 1
    stack = [0]
    todo = Set.new(1..goal)
    longest = -1
    shortest = 1 / 0.0
    while i = stack.pop
      each_neighbor(i, len, sqlen, todo) do |j, distance|
        longest = distance if longest < distance
        shortest = distance if distance < shortest
        return shortest, longest if j.equal?(goal)
        stack << j
      end
    end
    nil
  end

  def each_neighbor(i, len, sqlen, todo)
    @grid.each_neighbor(i, len) do |j|
      next unless todo.include?(j)
      distance = squared_distance_by_index(i, j)
      if distance <= sqlen
        yield j, distance
        todo.delete j
      end
    end
  end

  def squared_distance_by_index(ia, ib)
    ia, ib = ib, ia if ib < ia
    @distance_cache[ia * points.size + ib] ||= squared_distance(points[ia], points[ib])
  end

  def squared_distance(a, b)
    ax, ay = a
    bx, by = b
    (ax - bx) ** 2 + (ay - by) ** 2
  end
end

class Grid
  def initialize(points)
    @n = 5
    @ax, @ay, @bx, @by = aabb(points)
    @w = @bx - @ax
    @h = @by - @ay
    @cellw = @w / @n.to_r
    @cellh = @h / @n.to_r
    @points = points
    @bucket_of = points.map {|pt| which_bucket pt }
    @buckets = Array.new(@n * @n) { [] }
    @bucket_of.each_with_index {|b, i| @buckets[b] << i }
  end

  def aabb(points)
    ax = ay = bx = by = nil
    points.each do |x, y|
      ax = x if !ax || ax > x
      ay = y if !ay || ay > y
      bx = x if !bx || bx < x
      by = y if !by || by < y
    end
    return ax, ay, bx, by
  end

  def which_bucket(point)
    x, y = point
    by = @h == 0 ? @n - 1 : [(y - @ay) * @n / @h, @n - 1].min
    bx = @w == 0 ? @n - 1 : [(x - @ax) * @n / @w, @n - 1].min
    by * @n + bx
  end

  def each_neighbor(ipoint, radius)
    each_neighbor_bucket(ipoint, radius) do |bucket|
      @buckets[bucket].each {|i| yield i }
    end
  end
  
  def each_neighbor_bucket(ipoint, radius)
    bw = @cellw == 0 ? @n - 1 : [(radius / @cellw).ceil, @n - 1].min
    bh = @cellh == 0 ? @n - 1 : [(radius / @cellh).ceil, @n - 1].min
    b = @bucket_of[ipoint]
    bx = b % @n
    
    yield b

    (1..bw).each do |dx|
      yield b - dx if bx >= dx
      yield b + dx if bx + dx < @n
    end

    (1..bh).each do |dy|
      if (bpy = b - dy * @n) >= 0
        yield bpy
        
        (1..bw).each do |dx|
          yield bpy - dx if bx >= dx
          yield bpy + dx if bx + dx < @n
        end
      end

      if (bpy = b + dy * @n) < @n * @n
        yield bpy
        
        (1..bw).each do |dx|
          yield bpy - dx if bx >= dx
          yield bpy + dx if bx + dx < @n
        end
      end
    end
  end
end

Problem168.new((1..gets.to_i).map{gets.split.map(&:to_i)}).solve
0