ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1159. Fence

upper bound for binary search? why n*(sum of lengths) work?
Posted by muhammad 10 Apr 2011 13:53
i used 1e8 first and got wa14
latter used n*(sum of edge lengths) and got ac.

i found that for test 14 the curve goes up and at r=200.75 touches x axis then goes up until
x=around 450 then down again with asymptote as x axis. so i tried to use tenary search to find upper bound but it does not always work. why n*sum of lengths work? is it weak tests or can somebody prove optimal upper bound?

please, help me understand.
thanks in advance.