require 'bigdecimal' class UnionFind def initialize(n) @size = Array.new(n, 1) @parent = [] n.times do |i| @parent[i] = i end end def find(x) if @parent[x] == x x else @parent[x] = find(@parent[x]) end end def unite(x, y) x = find(x) y = find(y) return if x == y @parent[y] = x @size[x] += @size[y] end def same(x, y) find(x) == find(y) end def size(x) @size[find(x)] end end class PriorityQueue attr_reader :size def initialize(order: :asc) @size = 0 @nodes = [] @operator = (order == :asc) ? [:>, :<] : [:<, :>] end def empty? @size.zero? end def push(node) if @nodes[0].nil? @nodes[0] = node else index = size @nodes[index] = node loop { parent = (index-1)/2 if (@nodes[parent].last <=> node.last).public_send(@operator.first, 0) @nodes[index], @nodes[parent] = @nodes[parent], @nodes[index] index = parent break if index.zero? else break end } end @size += 1 end alias_method :<<, :push def pop node = @nodes.first @nodes[0], @nodes[size - 1] = @nodes[size - 1], nil index = 0 loop { left = 2*index+1 right = 2*index+2 if @nodes[left].nil? && @nodes[right].nil? break elsif @nodes[left] && @nodes[right] target = (@nodes[left].last <=> @nodes[right].last).public_send(@operator.last, 0) ? left : right if (@nodes[target].last <=> @nodes[index].last).public_send(@operator.last, 0) @nodes[index], @nodes[target] = @nodes[target], @nodes[index] index = target else break end elsif @nodes[left] if (@nodes[left].last <=> @nodes[index].last).public_send(@operator.last, 0) @nodes[index], @nodes[left] = @nodes[left], @nodes[index] index = left else break end elsif @nodes[right] if (@nodes[right].last <=> @nodes[index].last).public_send(@operator.last, 0) @nodes[index], @nodes[right] = @nodes[right], @nodes[index] index = right else break end end } @size -= 1 node.first end def top @nodes.first end end N = gets.to_i points = [] N.times do points << gets.chomp.split.map(&:to_i) end pque = PriorityQueue.new 0.upto(N-2) do |i| (i+1).upto(N-1) do |j| p1 = points[i] p2 = points[j] dist = BigDecimal((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2).sqrt(10) pque.push([[i, j, dist], dist]) end end check_list = {} max_d = 0 uf = UnionFind.new(N) until pque.empty? i, j, dist = pque.pop if uf.find(i) != uf.find(j) uf.unite(i, j) max_d = [max_d, dist].max break if uf.find(0) == uf.find(N-1) end end if max_d % 10 == 0 puts max_d.to_i else puts 10 * (max_d.to_i / 10 + 1) end