結果

問題 No.168 ものさし
ユーザー snipsnipsnipsnipsnipsnip
提出日時 2015-03-28 15:57:24
言語 Ruby
(3.3.0)
結果
RE  
実行時間 -
コード長 3,270 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 11,216 KB
実行使用メモリ 23,516 KB
最終ジャッジ日時 2023-09-11 10:46:14
合計ジャッジ時間 6,273 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 296 ms
17,204 KB
testcase_01 AC 83 ms
15,124 KB
testcase_02 RE -
testcase_03 AC 84 ms
15,228 KB
testcase_04 AC 85 ms
15,064 KB
testcase_05 AC 83 ms
15,120 KB
testcase_06 AC 83 ms
15,440 KB
testcase_07 AC 83 ms
15,240 KB
testcase_08 AC 82 ms
15,248 KB
testcase_09 AC 86 ms
15,340 KB
testcase_10 AC 96 ms
15,344 KB
testcase_11 AC 208 ms
17,212 KB
testcase_12 AC 251 ms
21,028 KB
testcase_13 AC 293 ms
23,476 KB
testcase_14 AC 126 ms
23,304 KB
testcase_15 AC 85 ms
15,328 KB
testcase_16 AC 86 ms
15,404 KB
testcase_17 AC 94 ms
15,532 KB
testcase_18 AC 92 ms
15,696 KB
testcase_19 AC 224 ms
23,324 KB
testcase_20 AC 179 ms
23,516 KB
testcase_21 AC 713 ms
23,500 KB
testcase_22 AC 466 ms
23,448 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
    [(y - @ay) * @n / @h, @n - 1].min * @n + [(x - @ax) * @n / @w, @n - 1].min
  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 = [(radius / @cellw).ceil, @n - 1].min
    bh = [(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