#会津大学オンラインジャッジ問0253 Ant Nestに合格したコード
#このコードには試行錯誤の過程が残っているので無駄な処理がある。
#気になった人はリファクタリングしてほしい
def group(as,n,h)
res=[]
n.times{|p1|
p2=(p1+1)%n
e1=as[p1]
e2=as[p2]
if e1[1]<=h && e2[1]<=h then
res<<e1
res<<e2
elsif h<e1[1] && h<e2[1] then
#何もしない
elsif e1[1]<=h && h<=e2[1] then
res<<e1
l1,l2=(e1[1]-h).abs,(h-e2[1]).abs
l3=l1+l2
l1a,l2a=l2/l3,l1/l3
res<<[e1[0]*l1a+e2[0]*l2a,e1[1]*l1a+e2[1]*l2a]
elsif h<=e1[1] && e2[1]<=h then
l1,l2=(e1[1]-h).abs,(h-e2[1]).abs
l3=l1+l2
l1a,l2a=l2/l3,l1/l3
res<<[e1[0]*l1a+e2[0]*l2a,e1[1]*l1a+e2[1]*l2a]
res<<e2
end
}
return res.uniq
end
def g(p1,p2,p3)
a1,a2=[p2,p3].map{|e| e.zip(p1).map{|e2| e2[0]-e2[1]}}
return (a1[0]*a2[1]-a2[0]*a1[1]).abs/2.0
end
def f2(as,sp,n)
res=0.0
n.times{|i|
p1=(sp+1+i)%n
p2=(sp+i+2)%n
res+=g(as[sp],as[p1],as[p2])
}
return res
end
def f(as,p1,n,t)
retirn 0 if t==0
as2=as.dup
as2=as2.map{|e| [e[0]-as[p1][0],e[1]-as[p1][1]]}
p2=(p1+1)%n
dx2=as2[p2][0]
dy2=as2[p2][1]
l1=Math.sqrt(dx2**2+dy2**2)
sin1=-dy2/l1
cos1=dx2/l1
as2=as2.map{|x,y| [cos1*x-sin1*y,sin1*x+cos1*y]}
h=0.0
as2.each{|x,y| h=[h,y].max}
return h if t>=f2(as2,p1,n)
return f3(0,0.0,h,t,as2,n,p1)
end
def f3(d,l,r,t,as,n,sp)
h=(l+r)/2.0
as2=group(as,n,h)
s1=f2(as2,sp,as2.size)
if d>60 || (s1-t).abs<0.000001 then
return h
end
if s1>t then
return f3(d+1,l,h,t,as,n,sp)
else
return f3(d+1,h,r,t,as,n,sp)
end
end
while true do
n,d,v=gets.chomp.split(" ")
n=n.to_i
break if n==0
t=v.to_f/d.to_f
as=[]
n.times{|e|
as<<gets.split(" ").map{|e| e.to_f}
}
ans=-1
n.times{|i|
t1=f(as,0,n,t)
if ans==-1 || ans<t1 then
ans=t1
end
as=as.rotate
}
puts sprintf("%.7f",ans)
end
I+S8mua0peWkp+WtpuOCquODs+ODqeOCpOODs+OCuOODo+ODg+OCuOWVjzAyNTMgQW50IE5lc3TjgavlkIjmoLzjgZfjgZ/jgrPjg7zjg4kKI+OBk+OBruOCs+ODvOODieOBq+OBr+ippuihjOmMr+iqpOOBrumBjueoi+OBjOaui+OBo+OBpuOBhOOCi+OBruOBp+eEoemnhOOBquWHpueQhuOBjOOBguOCi+OAggoj5rCX44Gr44Gq44Gj44Gf5Lq644Gv44Oq44OV44Kh44Kv44K/44Oq44Oz44Kw44GX44Gm44G744GX44GECmRlZiBncm91cChhcyxuLGgpCnJlcz1bXQpuLnRpbWVze3xwMXwKCXAyPShwMSsxKSVuCgllMT1hc1twMV0KCWUyPWFzW3AyXQoJCglpZiBlMVsxXTw9aCAmJiBlMlsxXTw9aCB0aGVuCgkJcmVzPDxlMQoJCXJlczw8ZTIKCWVsc2lmIGg8ZTFbMV0gJiYgaDxlMlsxXSB0aGVuCgkJI+S9leOCguOBl+OBquOBhAoJZWxzaWYgZTFbMV08PWggJiYgaDw9ZTJbMV0gdGhlbgoJCXJlczw8ZTEKCQlsMSxsMj0oZTFbMV0taCkuYWJzLChoLWUyWzFdKS5hYnMKCQlsMz1sMStsMgoJCWwxYSxsMmE9bDIvbDMsbDEvbDMKCQlyZXM8PFtlMVswXSpsMWErZTJbMF0qbDJhLGUxWzFdKmwxYStlMlsxXSpsMmFdCgllbHNpZiBoPD1lMVsxXSAmJiBlMlsxXTw9aCB0aGVuCgkJbDEsbDI9KGUxWzFdLWgpLmFicywoaC1lMlsxXSkuYWJzCgkJbDM9bDErbDIKCQlsMWEsbDJhPWwyL2wzLGwxL2wzCgkJcmVzPDxbZTFbMF0qbDFhK2UyWzBdKmwyYSxlMVsxXSpsMWErZTJbMV0qbDJhXQoJCXJlczw8ZTIKCWVuZAp9CnJldHVybiByZXMudW5pcQplbmQKZGVmIGcocDEscDIscDMpCglhMSxhMj1bcDIscDNdLm1hcHt8ZXwgZS56aXAocDEpLm1hcHt8ZTJ8IGUyWzBdLWUyWzFdfX0KCXJldHVybiAoYTFbMF0qYTJbMV0tYTJbMF0qYTFbMV0pLmFicy8yLjAKZW5kCmRlZiBmMihhcyxzcCxuKQoJcmVzPTAuMAoJbi50aW1lc3t8aXwKCQlwMT0oc3ArMStpKSVuCgkJcDI9KHNwK2krMiklbgoJCXJlcys9Zyhhc1tzcF0sYXNbcDFdLGFzW3AyXSkKCX0KCXJldHVybiByZXMKZW5kCmRlZiBmKGFzLHAxLG4sdCkKCXJldGlybiAwIGlmIHQ9PTAKCWFzMj1hcy5kdXAKCWFzMj1hczIubWFwe3xlfCBbZVswXS1hc1twMV1bMF0sZVsxXS1hc1twMV1bMV1dfQoJcDI9KHAxKzEpJW4KCWR4Mj1hczJbcDJdWzBdCglkeTI9YXMyW3AyXVsxXQoJbDE9TWF0aC5zcXJ0KGR4MioqMitkeTIqKjIpCglzaW4xPS1keTIvbDEKCWNvczE9ZHgyL2wxCglhczI9YXMyLm1hcHt8eCx5fCBbY29zMSp4LXNpbjEqeSxzaW4xKngrY29zMSp5XX0KCWg9MC4wCglhczIuZWFjaHt8eCx5fCBoPVtoLHldLm1heH0KCXJldHVybiBoIGlmIHQ+PWYyKGFzMixwMSxuKQoJcmV0dXJuIGYzKDAsMC4wLGgsdCxhczIsbixwMSkKZW5kCmRlZiBmMyhkLGwscix0LGFzLG4sc3ApCgloPShsK3IpLzIuMAoJYXMyPWdyb3VwKGFzLG4saCkKCXMxPWYyKGFzMixzcCxhczIuc2l6ZSkKCWlmIGQ+NjAgfHwgKHMxLXQpLmFiczwwLjAwMDAwMSB0aGVuCgkJcmV0dXJuIGgKCWVuZAoJaWYgczE+dCB0aGVuCgkJcmV0dXJuIGYzKGQrMSxsLGgsdCxhcyxuLHNwKQoJZWxzZQoJCXJldHVybiBmMyhkKzEsaCxyLHQsYXMsbixzcCkKCWVuZAplbmQKCndoaWxlIHRydWUgZG8KCW4sZCx2PWdldHMuY2hvbXAuc3BsaXQoIiAiKQoJCgluPW4udG9faQoJYnJlYWsgaWYgbj09MAoJdD12LnRvX2YvZC50b19mCglhcz1bXQoJbi50aW1lc3t8ZXwKCQlhczw8Z2V0cy5zcGxpdCgiICIpLm1hcHt8ZXwgZS50b19mfQoJfQoJYW5zPS0xCgluLnRpbWVze3xpfAoJCXQxPWYoYXMsMCxuLHQpCgkJaWYgYW5zPT0tMSB8fCBhbnM8dDEgdGhlbgoJCQlhbnM9dDEKCQllbmQKCQlhcz1hcy5yb3RhdGUKCX0KCXB1dHMgc3ByaW50ZigiJS43ZiIsYW5zKQplbmQ=