結果

問題 No.168 ものさし
ユーザー tshigtshig
提出日時 2016-08-20 09:58:30
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 361 ms
55,296 KB
testcase_01 AC 95 ms
12,416 KB
testcase_02 AC 79 ms
12,416 KB
testcase_03 AC 82 ms
12,416 KB
testcase_04 AC 81 ms
12,416 KB
testcase_05 AC 81 ms
12,288 KB
testcase_06 AC 78 ms
12,544 KB
testcase_07 AC 82 ms
12,416 KB
testcase_08 AC 80 ms
12,416 KB
testcase_09 AC 86 ms
12,672 KB
testcase_10 AC 96 ms
13,696 KB
testcase_11 AC 208 ms
27,776 KB
testcase_12 AC 511 ms
51,088 KB
testcase_13 AC 662 ms
66,688 KB
testcase_14 AC 567 ms
66,688 KB
testcase_15 AC 86 ms
12,544 KB
testcase_16 AC 85 ms
12,544 KB
testcase_17 AC 92 ms
13,184 KB
testcase_18 AC 109 ms
14,976 KB
testcase_19 AC 635 ms
64,792 KB
testcase_20 AC 616 ms
65,536 KB
testcase_21 AC 665 ms
68,536 KB
testcase_22 AC 675 ms
69,564 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