ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1256. Кладбищенский сторож

How to solve this problem? (-)
Послано Krayev Alexey (PSU) 10 авг 2006 21:38
Re: How to solve this problem? (-)
Послано blue shading 19 авг 2006 22:46
Does binary search work?
Re: How to solve this problem? (-)
Послано Vedernikoff Sergey 24 авг 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...
Re: How to solve this problem? (-)
Послано KAV 24 авг 2006 13:04
I tried to use 2 binary searches, but WA :(
Re: How to solve this problem?
Послано Krayev Alexey (PSU) 24 авг 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
Re: How to solve this problem?
Послано Vedernikoff Sergey 1 сен 2006 21:32
Krayev Alexey (PSU) писал(a) 24 августа 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.
Re: How to solve this problem?
Послано svr 30 июн 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
Re: How to solve this problem?
Послано Denis Koshman 28 авг 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".
Re: How to solve this problem? (-)
Послано SkorKNURE 8 окт 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 :)
Re: How to solve this problem?
Послано xurshid_n 31 мар 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