結果

問題 No.168 ものさし
ユーザー tshigtshig
提出日時 2016-08-20 09:58:30
言語 Ruby
(3.3.0)
結果
AC  
実行時間 682 ms / 2,000 ms
コード長 1,119 bytes
コンパイル時間 86 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 69,436 KB
最終ジャッジ日時 2024-06-06 15:05:36
合計ジャッジ時間 7,362 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 341 ms
55,296 KB
testcase_01 AC 79 ms
12,416 KB
testcase_02 AC 76 ms
12,416 KB
testcase_03 AC 75 ms
12,544 KB
testcase_04 AC 76 ms
12,544 KB
testcase_05 AC 77 ms
12,416 KB
testcase_06 AC 76 ms
12,544 KB
testcase_07 AC 78 ms
12,416 KB
testcase_08 AC 78 ms
12,288 KB
testcase_09 AC 90 ms
12,672 KB
testcase_10 AC 100 ms
13,568 KB
testcase_11 AC 211 ms
27,776 KB
testcase_12 AC 491 ms
51,072 KB
testcase_13 AC 660 ms
66,688 KB
testcase_14 AC 560 ms
66,560 KB
testcase_15 AC 81 ms
12,544 KB
testcase_16 AC 83 ms
12,672 KB
testcase_17 AC 90 ms
13,184 KB
testcase_18 AC 107 ms
14,976 KB
testcase_19 AC 659 ms
64,764 KB
testcase_20 AC 630 ms
65,408 KB
testcase_21 AC 679 ms
68,576 KB
testcase_22 AC 682 ms
69,436 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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