fork download
copy 
  1. #会津大学オンラインジャッジ問0342　Road Planningに合格したコード、Rubyで通ったのは私だけ。
  2. def f3(a,b)
  3. 	dx=(a[0]-b[0]).abs
  4. 	dy=(a[1]-b[1]).abs
  5. 	return Math.sqrt(dx**2+dy**2)
  6. end
  7.  
  8. def g(as,e1,e2)
  9. 	dx2=e2[0]-e1[0]
  10. 	dy2=e2[1]-e1[1]
  11. 	as.each{|e3|
  12. 		next if e1==e3 || e2==e3
  13. 		dx3=e3[0]-e1[0]
  14. 		dy3=e3[1]-e1[1]
  15. 		g1=dx2*dy3-dx3*dy2
  16. 		return false if g1<0.0
  17. 	}
  18. 	return true
  19. end
  20. def f(as,gs)
  21. 	p1=as.min
  22. 	logp=[p1]
  23. 	gs2={}
  24. 	hs={}
  25. 	hs[p1]=0
  26. 	hit=true
  27. 	l1=0.0
  28. 	while hit do
  29. 		hit=false
  30. 		as.each{|e|
  31. 			next if hs.member?(e)
  32. 			next if g(as,p1,e)==false
  33. 			logp<<e
  34. 			hs[e]=0
  35. 			hit=true
  36. 			l1+=f3(p1,e)
  37. 			p1=e
  38. 			break
  39. 		}
  40. 	end
  41. 	l1+=f3(logp[0],logp.last)
  42. 	logp.each{|e|
  43. 		if gs.member?(e) then
  44. 			gs[e].each{|e2|
  45. 				next if hs.member?(e2)
  46. 				t1=f3(e,e2)
  47. 				gs2[t1]=[] if gs2.member?(t1)==false
  48. 				gs2[t1]<<e2
  49. 			}
  50. 		end
  51. 	}
  52.  
  53. 	return [gs2,hs,l1]
  54. end
  55.  
  56. n,m=gets.split(" ").map{|e| e.to_i}
  57. as=[]
  58. n.times{
  59. 	as<<gets.split(" ").map{|e| e.to_f}
  60. }
  61.  
  62. gs={}
  63. m.times{
  64. 	a,b=gets.split(" ").map{|e| as[e.to_i-1]}
  65. 	gs[a]=[] if gs.member?(a)==false
  66. 	gs[b]=[] if gs.member?(b)==false
  67. 	gs[a]<<b
  68. 	gs[b]<<a
  69. }
  70. gs2,hs2,l2= f(as,gs)
  71.  
  72. while hs2.size<n do
  73. 	ts1=gs2.min
  74. 	t2=ts1[0]
  75. 	es=ts1[1]
  76. 	if es.size==0 then
  77. 		gs2.delete(t2)
  78. 	else
  79. 		hit=false
  80. 		while gs2[t2].size>0 do
  81. 			e2=gs2[t2].shift
  82. 			next if hs2.member?(e2)
  83. 			hit=true
  84. 			hs2[e2]=0
  85. 			l2+=t2
  86. 			if hs2.size==n then
  87. 				break
  88. 			end
  89. 			gs[e2].each{|e3|
  90. 				next if hs2.member?(e3)
  91. 				t2=f3(e2,e3)
  92. 				gs2[t2]=[] if gs2.member?(t2)==false
  93. 				gs2[t2]<<e3
  94. 			}
  95. 			break if hit==true
  96. 		end
  97. 	end
  98. end
  99. puts sprintf("%.4f",l2)
Success #stdin #stdout 0.01s 6484KB
comments (?)
stdin
copy 
7 6
0 2
3 0
2 2
1 0
4 1
2 3
3 5
1 3
2 4
2 3
3 5
3 7
6 7
stdout
copy 
18.2521
https://ideone.com/YBEiHg
language:
Ruby (ruby 2.5.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!