結果

問題 No.168 ものさし
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-08 05:45:31
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,547 ms / 2,000 ms
コード長 1,527 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 130,940 KB
最終ジャッジ日時 2024-12-24 07:18:19
合計ジャッジ時間 14,952 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

# frozen_string_literal: true
require 'bigdecimal'
module Graph
  class Node
    attr_reader :id, :x, :y
    def initialize(id, x, y)
      @id = id
      @x = x
      @y = y
      @parent = self
    end
    def powered_length(other)
      (@x - other.x)**2 + (@y - other.y)**2
    end
    def founder?
      @parent == self
    end
    def ancestor
      if founder?
        self
      else
        @parent.ancestor
      end
    end
    def same?(other)
      ancestor == other.ancestor
    end
    def union!(other)
      if founder?
        if ancestor.id >= other.ancestor.id
          @parent = other.ancestor
        else
          other.union!(self)
        end
      else
        @parent.ancestor.union!(other)
      end
    end
  end
  class Edge
    attr_reader :weight
    def initialize(a, b)
      @a = a
      @b = b
      @weight = @a.powered_length(@b)
    end
    def same?
      @a.same?(@b)
    end
    def union!
      @a.union!(@b)
    end
  end
end

def int_sqrt(n, k)
  BigDecimal(n).sqrt(Math.log10(n).to_i).ceil(k).to_i
end

n = gets.to_i
list = Array.new(n) { gets.split.map(&:to_i)}

node_list = list.each_with_index
  .map { |xy, i| Graph::Node.new(i, xy[0], xy[1]) }
edge_list = node_list.product(node_list)
  .reject { |a, b| a == b }
  .map { |a, b| Graph::Edge.new(a, b) }
  .sort_by(&:weight)

max_weight = 0
edge_list.each do |edge|
  break if node_list.last.ancestor == node_list.first
  unless edge.same?
    edge.union!
    max_weight = edge.weight
  end
end
puts int_sqrt(max_weight, -1)
0