結果

問題 No.168 ものさし
コンテスト
ユーザー らっしー(raccy)
提出日時 2017-03-08 05:30:21
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,384 bytes
コンパイル時間 109 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 131,192 KB
最終ジャッジ日時 2024-06-23 20:51:42
合計ジャッジ時間 13,218 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 parent
      if @parent == self
        self
      else
        @parent.parent
      end
    end
    def same?(other)
      @parent == other.parent
    end
    def union!(other)
      if parent.id >= other.parent.id
        @parent = other.parent
      else
        other.union!(self)
      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!
      @b.union!(@a)
    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.parent == node_list.first
  unless edge.same?
    edge.union!
    max_weight = edge.weight
  end
end
puts int_sqrt(max_weight, -1)
0