結果

問題 No.168 ものさし
ユーザー らっしー(raccy)らっしー(raccy)
提出日時 2017-03-08 05:45:31
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,548 ms / 2,000 ms
コード長 1,527 bytes
コンパイル時間 509 ms
コンパイル使用メモリ 11,292 KB
実行使用メモリ 149,052 KB
最終ジャッジ日時 2023-08-25 21:05:10
合計ジャッジ時間 13,656 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 381 ms
46,192 KB
testcase_01 AC 79 ms
15,548 KB
testcase_02 AC 81 ms
15,432 KB
testcase_03 AC 80 ms
15,524 KB
testcase_04 AC 81 ms
15,660 KB
testcase_05 AC 80 ms
15,664 KB
testcase_06 AC 81 ms
15,420 KB
testcase_07 AC 80 ms
15,452 KB
testcase_08 AC 78 ms
15,428 KB
testcase_09 AC 86 ms
15,980 KB
testcase_10 AC 116 ms
18,624 KB
testcase_11 AC 360 ms
43,364 KB
testcase_12 AC 1,027 ms
112,728 KB
testcase_13 AC 1,546 ms
148,964 KB
testcase_14 AC 1,548 ms
148,916 KB
testcase_15 AC 80 ms
15,544 KB
testcase_16 AC 86 ms
15,920 KB
testcase_17 AC 99 ms
16,860 KB
testcase_18 AC 147 ms
21,880 KB
testcase_19 AC 1,392 ms
148,340 KB
testcase_20 AC 1,537 ms
148,948 KB
testcase_21 AC 1,536 ms
149,052 KB
testcase_22 AC 1,546 ms
148,976 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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