| ENG RUS | Timus Online Judge |
Обсуждение задачи 1256. Кладбищенский сторожShen Yang it is not geometry problem, just reading comprehension // Задача 1256. Кладбищенский сторож 10 окт 2018 13:38 yuzeming Why WA7? [1] // Задача 1256. Кладбищенский сторож 2 апр 2010 17:00 Why WA7? bsu.mmf.team Re: Why WA7? // Задача 1256. Кладбищенский сторож 12 авг 2016 19:13 Test 7 is something like: 20 50 40 30 answer is 40.000 (not 20.000 xD) zmj159 WA#14 and have no idea // Задача 1256. Кладбищенский сторож 14 дек 2015 08:33 I think I have considered all possible special situations, but don't know any other tricks. And I think it must be a trick about precision. example12 WA2 // Задача 1256. Кладбищенский сторож 20 апр 2013 05:22 Programm works for all tests from http://acm.timus.ru/forum/thread.aspx?id=21527&upd=634549751157862771 but i still have WA2. Please, help. Edited by author 20.04.2013 05:23 NewGeneration Need some tests! Help please! // Задача 1256. Кладбищенский сторож 4 мар 2013 04:15 Can you help me? Tried different tests and answers are right, but here...every time I read the same: "Wrong answer". Krayev Alexey (PSU) How to solve this problem? (-) [9] // Задача 1256. Кладбищенский сторож 10 авг 2006 21:38 blue shading Re: How to solve this problem? (-) [6] // Задача 1256. Кладбищенский сторож 19 авг 2006 22:46 Does binary search work? Vedernikoff Sergey Re: How to solve this problem? (-) [5] // Задача 1256. Кладбищенский сторож 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... Krayev Alexey (PSU) Re: How to solve this problem? [4] // Задача 1256. Кладбищенский сторож 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 Vedernikoff Sergey Re: How to solve this problem? [3] // Задача 1256. Кладбищенский сторож 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 ? To use binary search to find minimum/maximum function is not obliged to be monotonic. And it will not be monotonic, really.And what advanced :) geometry do u mean? Edited by author 24.08.2006 22:55 svr Re: How to solve this problem? [2] // Задача 1256. Кладбищенский сторож 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 Denis Koshman Re: How to solve this problem? // Задача 1256. Кладбищенский сторож 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". xurshid_n Re: How to solve this problem? // Задача 1256. Кладбищенский сторож 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 KAV Re: How to solve this problem? (-) // Задача 1256. Кладбищенский сторож 24 авг 2006 13:04 I tried to use 2 binary searches, but WA :( SkorKNURE Re: How to solve this problem? (-) // Задача 1256. Кладбищенский сторож 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 :) vano_B1 IS It possible to solve this problem by geometry? [1] // Задача 1256. Кладбищенский сторож 10 июн 2005 16:11 Subj. Thanks. Edric Mao Re: IS It possible to solve this problem by geometry? // Задача 1256. Кладбищенский сторож 24 окт 2011 16:28 I want to know,too. Rumter (3) hints [2] // Задача 1256. Кладбищенский сторож 29 ноя 2008 18:23 If you get WA4 or WA5: eps = 1e-6; if (r1 + r2 == r3) print ((r1 - r4) * 2 + (r2 - r4) * 2); If you get WA6: WA: printf ("%.7lf", ans); AC: printf ("%.3lf", ans); if you get WA7 and etc your wrong in functions: asin, acos. Rumter (3) tests // Задача 1256. Кладбищенский сторож 29 ноя 2008 18:27 r1 r2 r3 r4 ans 10000 10000 10000 1 29996.536 30 70 40 2 136 4 5 1 1 8 2 2 4 2 0 5 5 8 1 14.227 30 32 15 10 25 47.076 5 5 6 3 5.760 5 5 6 6 0.000 5000 5000 8000 1 17996.205 25 35 30 2 83.245 1000 1000 2000 250 3000.000 234 34 240 1 504.433 1000 2000 1000 250 3500.000 Edric Mao Re: hints // Задача 1256. Кладбищенский сторож 23 окт 2011 13:58 thanks hedrok To admins: My AC solution fails on some tests // Задача 1256. Кладбищенский сторож 28 июл 2008 23:00 To admins: i think this test should be added (or any other where r3 = 0): 11 11 0 1 right answer: 20.000 i've found out that i am dividing by r3, but don't check whether r3 is zero. Not to admins: While solving i was short of normal tests (not special cases), so here are some: 234 34 240 1 answer: 504.433 25 35 30 2 answer: 83.245 i used two nested modified a little binary searches. Edited by author 28.07.2008 23:01 Aleksey (BMSTU IU7) Help... [1] // Задача 1256. Кладбищенский сторож 13 июл 2003 21:10 if not(((R1<=R4) or (R2<=R4)) or (R3=0)) then solve-path is some triangle with vertexes: at house and on two circles R3-radius?????? Vedernikoff Sergey Re: Help... // Задача 1256. Кладбищенский сторож 8 авг 2006 18:08 Not always, but as partial case - yes... Victor Barinov (TNU) Help, Please! Give me some tests plz. (+) [2] // Задача 1256. Кладбищенский сторож 21 ноя 2005 03:11 I have WA on test 3. I need godd tests. Help me please. Thanks! Shambala Maybe it will Help (+) [1] // Задача 1256. Кладбищенский сторож 22 ноя 2005 02:01 Test1: 500 1000 500 250 Test2: 1000 600 600 400 Test3: 0 0 0 r frost Re: Maybe it will Help (+) // Задача 1256. Кладбищенский сторож 28 июл 2006 14:59 what are the answers? Agh Is this problem equivalent to another one? [1] // Задача 1256. Кладбищенский сторож 10 сен 2003 20:04 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. TIA, agh Agh Obviously no // Задача 1256. Кладбищенский сторож 11 сен 2003 21:05 Cause the task is the same but the square where distance is zero decreade by two. Dmitry 'Diman_YES' Kovalioff I've got AC using double binary search with subsequences (-) // Задача 1256. Кладбищенский сторож 21 мар 2003 18:28 Perov Rodion Народ!!!! [1] // Задача 1256. Кладбищенский сторож 18 мар 2003 20:36 Слушайте ну помоему задачка-то несерьезная. Но тока пока я ее не решил но это не важно))))) Карроче- переходим к кординатному методу. Ну есенно парочку условий- ну если они на одной прямой то все понятно- если домик внутри окружности цепи тоже вроде все ок и остальное: если цепи пересекаются то к точке пересечения и обратно если нет то два варианта- какой из них короче сказать не могу но это машинным способом проверить можно Тк вот первы Leonid Volkov Use English please (-) // Задача 1256. Кладбищенский сторож 19 мар 2003 11:36 nicushor do u know how to solve it? // Задача 1256. Кладбищенский сторож 17 мар 2003 16:01 do u know how to solve it? i don't........ nicushor do u know how to solve it? // Задача 1256. Кладбищенский сторож 17 мар 2003 16:00 ratrax21 i've got AC // Задача 1256. Кладбищенский сторож 17 мар 2003 14:47 if you want the solution e-mail me to Daniciuc_Marian@yahoo.com
|