def max(d,n) m = d.flatten.compact.sort{|a,b|b<=>a}[n] p1 = nil p2 = nil d.find.with_index{|r,i| p1 = i r.find.with_index{|c,j| p2 = j c == m } } [p1,p2,m] end def dfs(d,s,g,di) check = Array.new(N,false) stack = [] stack.push(s) goal = false while stack.size > 0 nx = stack.pop() check[nx] = true if nx == g goal = true break end cand = d[nx].map.with_index{|e,i|nx==i ? nil : e} cand.map.with_index{|e,i| stack.push(i) if !e.nil? && e <= 10.0 && !check[i]} end return goal # cand = d[s].map.with_index{|e,i|f==i ? nil : e} # cand.map.with_index{|e,i| !e.nil? && e <= 10.0 && !c[i] ? dfs(d,i,g,e,s,c) : false}.include?(true) end N=gets.to_i pos=[] N.times{pos.push(gets.split(/\s/).map(&:to_i))} d=Array.new(pos.size).map{Array.new(pos.size)} N.times{|i| N.times{|k| d[i][k]=((pos[i][0]-pos[k][0])**2+(pos[i][1]-pos[k][1])**2)**0.5 if i != k}} case(d.size) when 0 then puts 1 when 1 then puts 2 when 2 then puts d[0][1] <= 10.0 ? d[0][1]+2 : 2 else f = false (0..d.flatten.compact.size/2).each{|num| s,g,d0 = max(d,num) if dfs(d,s,g,d0) f = true puts d0+2 break end } puts 1 unless f end