Does binary search work?

Yes, you can solve this problem using 2 binary searches.
Or, applying advanced geometry, this problem can be solved with 1 binary search...

I tried to use 2 binary searches, but WA :(

to use binary search function must be monotonic. why will the function be monotonic ?
And what advanced :) geometry do u mean?


Edited by author 24.08.2006 22:55

To use binary search to find minimum/maximum function is not obliged to be monotonic. And it will not be monotonic, really.

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.

Edited by author 30.06.2007 11:32

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".

Comment from my source:

/*
 * 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 :)

Thanks to svr very lot. AC!!!!

Edited by author 31.03.2012 10:44

Edited by author 31.03.2012 10:44