結果

問題 No.168 ものさし
ユーザー tshigtshig
提出日時 2016-08-20 09:58:30
言語 Ruby
(3.3.0)
結果
AC  
実行時間 814 ms / 2,000 ms
コード長 1,119 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 11,400 KB
実行使用メモリ 76,424 KB
最終ジャッジ日時 2023-08-25 21:02:10
合計ジャッジ時間 8,581 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 351 ms
59,424 KB
testcase_01 AC 80 ms
15,524 KB
testcase_02 AC 79 ms
15,336 KB
testcase_03 AC 80 ms
15,552 KB
testcase_04 AC 80 ms
15,460 KB
testcase_05 AC 81 ms
15,584 KB
testcase_06 AC 80 ms
15,568 KB
testcase_07 AC 79 ms
15,492 KB
testcase_08 AC 82 ms
15,564 KB
testcase_09 AC 87 ms
15,620 KB
testcase_10 AC 97 ms
16,792 KB
testcase_11 AC 236 ms
30,876 KB
testcase_12 AC 579 ms
58,468 KB
testcase_13 AC 756 ms
76,060 KB
testcase_14 AC 649 ms
76,084 KB
testcase_15 AC 79 ms
15,580 KB
testcase_16 AC 84 ms
15,756 KB
testcase_17 AC 90 ms
16,088 KB
testcase_18 AC 117 ms
18,016 KB
testcase_19 AC 759 ms
74,204 KB
testcase_20 AC 752 ms
76,364 KB
testcase_21 AC 814 ms
76,360 KB
testcase_22 AC 799 ms
76,424 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