Hi,
I was just working on BOI 2012 and this is my accepted solution. For some reason in my binary search, there seems to be a strange floating point thing.
Line 81, cout << fixed << setprecision(9) << left << "\n"; has a precision of 10^{-9}. It seems like the precision has to be at least 10^{-4}, which makes sense considering the accuracy according to the problem statement must be at least 10^{-3}.
Line 69 is the weird one. It is while (right - left >= 1e-3). For some reason, my code only works if this precision is between 10^{-3} and 10^{-7} (inclusive). But my question is: why does there need to be an upper bound and why can it not be, say, 10^{-9} ?
after an iteration of the while loop, left and right do not change.
which causes your solution to TLE.
For example, when I tried running on one of the test cases I ended up with:
left\approx 9570930.27488137968
right \approx 9570930.27488138154
middle =right
right gets set to middle
Why does middle equal right here? It’s because there is no number in between left and right that can be represented in double precision. In general, the quotient of two consecutive numbers exactly representable in double precision will be on the order of 1+2^{-52}, where 52 is the number of bits of significand precision:
You can verify yourself that right/left-1 is on the order of 2^{-52}:
If you change the threshold from 10^{-9} to 10^{-3}, then the while loop will terminate before left and right get too close to each other, so it is always guaranteed that middle will be strictly between left and right and the loop will make progress.