fork download
  1. #会津大学オンラインジャッジ問0253 Ant Nestに合格したコード
  2. #このコードには試行錯誤の過程が残っているので無駄な処理がある。
  3. #気になった人はリファクタリングしてほしい
  4. def group(as,n,h)
  5. res=[]
  6. n.times{|p1|
  7. p2=(p1+1)%n
  8. e1=as[p1]
  9. e2=as[p2]
  10.  
  11. if e1[1]<=h && e2[1]<=h then
  12. res<<e1
  13. res<<e2
  14. elsif h<e1[1] && h<e2[1] then
  15. #何もしない
  16. elsif e1[1]<=h && h<=e2[1] then
  17. res<<e1
  18. l1,l2=(e1[1]-h).abs,(h-e2[1]).abs
  19. l3=l1+l2
  20. l1a,l2a=l2/l3,l1/l3
  21. res<<[e1[0]*l1a+e2[0]*l2a,e1[1]*l1a+e2[1]*l2a]
  22. elsif h<=e1[1] && e2[1]<=h then
  23. l1,l2=(e1[1]-h).abs,(h-e2[1]).abs
  24. l3=l1+l2
  25. l1a,l2a=l2/l3,l1/l3
  26. res<<[e1[0]*l1a+e2[0]*l2a,e1[1]*l1a+e2[1]*l2a]
  27. res<<e2
  28. end
  29. }
  30. return res.uniq
  31. end
  32. def g(p1,p2,p3)
  33. a1,a2=[p2,p3].map{|e| e.zip(p1).map{|e2| e2[0]-e2[1]}}
  34. return (a1[0]*a2[1]-a2[0]*a1[1]).abs/2.0
  35. end
  36. def f2(as,sp,n)
  37. res=0.0
  38. n.times{|i|
  39. p1=(sp+1+i)%n
  40. p2=(sp+i+2)%n
  41. res+=g(as[sp],as[p1],as[p2])
  42. }
  43. return res
  44. end
  45. def f(as,p1,n,t)
  46. retirn 0 if t==0
  47. as2=as.dup
  48. as2=as2.map{|e| [e[0]-as[p1][0],e[1]-as[p1][1]]}
  49. p2=(p1+1)%n
  50. dx2=as2[p2][0]
  51. dy2=as2[p2][1]
  52. l1=Math.sqrt(dx2**2+dy2**2)
  53. sin1=-dy2/l1
  54. cos1=dx2/l1
  55. as2=as2.map{|x,y| [cos1*x-sin1*y,sin1*x+cos1*y]}
  56. h=0.0
  57. as2.each{|x,y| h=[h,y].max}
  58. return h if t>=f2(as2,p1,n)
  59. return f3(0,0.0,h,t,as2,n,p1)
  60. end
  61. def f3(d,l,r,t,as,n,sp)
  62. h=(l+r)/2.0
  63. as2=group(as,n,h)
  64. s1=f2(as2,sp,as2.size)
  65. if d>60 || (s1-t).abs<0.000001 then
  66. return h
  67. end
  68. if s1>t then
  69. return f3(d+1,l,h,t,as,n,sp)
  70. else
  71. return f3(d+1,h,r,t,as,n,sp)
  72. end
  73. end
  74.  
  75. while true do
  76. n,d,v=gets.chomp.split(" ")
  77.  
  78. n=n.to_i
  79. break if n==0
  80. t=v.to_f/d.to_f
  81. as=[]
  82. n.times{|e|
  83. as<<gets.split(" ").map{|e| e.to_f}
  84. }
  85. ans=-1
  86. n.times{|i|
  87. t1=f(as,0,n,t)
  88. if ans==-1 || ans<t1 then
  89. ans=t1
  90. end
  91. as=as.rotate
  92. }
  93. puts sprintf("%.7f",ans)
  94. end
Success #stdin #stdout 0.02s 6444KB
stdin
4 1 100000
0 0
1000 0
1000 1000
0 1000
0 0 0
stdout
100.0000000