Discussion @ 1256. Cemetery Guard @ Timus Online Judge

Shen Yang it is not geometry problem, just reading comprehension // Problem 1256. Cemetery Guard 10 Oct 2018 13:38

yuzeming Why WA7? [1] // Problem 1256. Cemetery Guard 2 Apr 2010 17:00

zmj159 WA#14 and have no idea // Problem 1256. Cemetery Guard 14 Dec 2015 08:33

mnzhkv WA2 // Problem 1256. Cemetery Guard 20 Apr 2013 05:22

NewGeneration Need some tests! Help please! // Problem 1256. Cemetery Guard 4 Mar 2013 04:15

Kraev Alexey How to solve this problem? (-) [9] // Problem 1256. Cemetery Guard 10 Aug 2006 21:38

blue shading Re: How to solve this problem? (-) [6] // Problem 1256. Cemetery Guard 19 Aug 2006 22:46

Does binary search work?

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: How to solve this problem? (-) [5] // Problem 1256. Cemetery Guard 24 Aug 2006 00:24

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

Kraev Alexey Re: How to solve this problem? [4] // Problem 1256. Cemetery Guard 24 Aug 2006 22:36

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

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: How to solve this problem? [3] // Problem 1256. Cemetery Guard 1 Sep 2006 21:32

Kraev Alexey wrote 24 August 2006 22:36

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.

svr Re: How to solve this problem? [2] // Problem 1256. Cemetery Guard 30 Jun 2007 11:32

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

Denis Koshman Re: How to solve this problem? // Problem 1256. Cemetery Guard 28 Aug 2008 14:10

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

coder Re: How to solve this problem? // Problem 1256. Cemetery Guard 31 Mar 2012 10:43

Thanks to svr very lot. AC!!!!

Edited by author 31.03.2012 10:44

Edited by author 31.03.2012 10:44

KAV Re: How to solve this problem? (-) // Problem 1256. Cemetery Guard 24 Aug 2006 13:04

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

SkorKNURE Re: How to solve this problem? (-) // Problem 1256. Cemetery Guard 8 Oct 2010 05:25

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

vano_B1 IS It possible to solve this problem by geometry? [1] // Problem 1256. Cemetery Guard 10 Jun 2005 16:11

Rumter (3) hints [2] // Problem 1256. Cemetery Guard 29 Nov 2008 18:23

hedrok <ONPU> Odesa To admins: My AC solution fails on some tests // Problem 1256. Cemetery Guard 28 Jul 2008 23:00

Vassenbaher [IU7.BMSTU] Help... [1] // Problem 1256. Cemetery Guard 13 Jul 2003 21:10

Victor Barinov (TNU) Help, Please! Give me some tests plz. (+) [2] // Problem 1256. Cemetery Guard 21 Nov 2005 03:11

opestov Is this problem equivalent to another one? [1] // Problem 1256. Cemetery Guard 10 Sep 2003 20:04

Dmitry 'Diman_YES' Kovalioff. Retired I've got AC using double binary search with subsequences (-) // Problem 1256. Cemetery Guard 21 Mar 2003 18:28

Perov Rodion Народ!!!! [1] // Problem 1256. Cemetery Guard 18 Mar 2003 20:36

IMX do u know how to solve it? // Problem 1256. Cemetery Guard 17 Mar 2003 16:01

IMX do u know how to solve it? // Problem 1256. Cemetery Guard 17 Mar 2003 16:00

ratrax21 i've got AC // Problem 1256. Cemetery Guard 17 Mar 2003 14:47

Discussion of Problem 1256. Cemetery Guard