結果

問題 No.168 ものさし
ユーザー tshig
提出日時 2016-08-20 09:58:30
言語 Ruby
(3.4.1)
結果
AC  
実行時間 675 ms / 2,000 ms
コード長 1,119 bytes
コンパイル時間 117 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 69,564 KB
最終ジャッジ日時 2024-12-24 07:14:34
合計ジャッジ時間 7,387 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

require 'bigdecimal'

class Calc0168
  def initialize(args)
    args = args.map { |l| l.chomp.split(/\s+/) }
    @n = args.shift.first.to_i
    @xys = args.map { |l| l.map(&:to_i) }
  end

  def calc
    graph = []
    (0...@n).each do |i|
      ((i + 1)...@n).each do |j|
        ds = (@xys[i][0] - @xys[j][0]) ** 2 + (@xys[i][1] - @xys[j][1]) ** 2
        graph << [[i, j], ds]
      end
    end
    graph.sort_by! { |g| g[1] }

    connects = []
    graph.each do |p, d|
      i1 = connects.index { |c|
        c.include?(p[0]) || c.include?(p[1])
      }
      if i1
        connects[i1] += p
        i2 = connects.drop(i1 + 1).index { |c|
          c.include?(p[0]) || c.include?(p[1])
        }
        if i2
          c = connects.delete_at(i1 + 1 + i2)
          connects[i1] += c
        end
      else
        connects << p
      end

      return d if connects.any? { |connect|
        connect.include?(0) && connect.include?(@n - 1)
      }
    end
  end

  def run
    r = calc
    (BigDecimal(r).sqrt(Math.log10(r).to_i) / 10).ceil * 10
  end
end

puts Calc0168.new(STDIN.readlines).run if __FILE__ == $0
0