I got Ac very very easy without binary search. I used sequentul optimization on rectangle [0,2*pi][0,2*pi] by angle variables s,t . At beggining dt=pi - size of window for search,s0=pi,t0=pi-it's centre. Use N=100 steps by each variable. Let sRec,tRec- point of Record on first step. For next step we do: s0=sRec;t0=tRex,dt=dt/10- moving and diminishing search-window. And so on while dt>0.000001.
Binary search is applicable only to monotonic functions and functions having one minimum. Otherwise you are not protected against falling into local minimum pit. Same stands for gradient slide. Yes, you can protected yourself with a lot of small ranges (up to TL), but that's a "lucky way".
/* * Using the law of cosines set to point O, A, B * any valid coords on the plane. Build circle C1 around * point A and C2 - around B. Consider all points from C1 * with a some small step. For each such point A' find * corresponding point B' on C2 that minimize distance * OA' + A'B' + B'O. For finding it we can also iterate * all points from C2 with certain step and compute * final distance for such pair (A', B'). But if we set * enough precision (a very small step) to attain a correct * answet - then obviously would earn "time limit". * We can avoid it e.g. in next way: * Instead of making only one pass with very small step * throug both circles we can make several passes recursively - * first will be over all points with big step, second - over * some small range near the local minimum obtained on previous * pass and so one... */
Maybe this will help to anyone... P.S.: in test 7 OA = 0, in test 8 - OB = 0. Or vise versa. On test >= 10 problems with precision can appear everywhere :)
In which we have two points (dogs' poles) and one circle with center in guard's house and radius R4. The task is to pass both points but the distance between any two points inside circle is equal to zero. And initially guard is sitiuated in his house.