結果

問題 No.94 圏外です。(EASY)
コンテスト
ユーザー LED
提出日時 2019-01-28 16:15:42
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,155 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 90 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 37,800 KB
最終ジャッジ日時 2024-10-04 20:38:22
合計ジャッジ時間 7,241 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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
0