| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| it is not geometry problem, just reading comprehension | Shen Yang | 1256. Кладбищенский сторож | 10 окт 2018 13:38 | 1 |
|
| Why WA7? | yuzeming | 1256. Кладбищенский сторож | 12 авг 2016 19:13 | 2 |
Test 7 is something like:
20 50 40
30
answer is 40.000 (not 20.000 xD) |
| WA#14 and have no idea | zmj159 | 1256. Кладбищенский сторож | 14 дек 2015 08:33 | 1 |
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. |
| WA2 | example12 | 1256. Кладбищенский сторож | 20 апр 2013 05:22 | 1 |
WA2 example12 20 апр 2013 05:22 |
| Need some tests! Help please! | NewGeneration | 1256. Кладбищенский сторож | 4 мар 2013 04:15 | 1 |
Can you help me? Tried different tests and answers are right, but here...every time I read the same: "Wrong answer". |
| How to solve this problem? (-) | Krayev Alexey (PSU) | 1256. Кладбищенский сторож | 31 мар 2012 10:43 | 10 |
Yes, you can solve this problem using 2 binary searches.
Or, applying advanced geometry, this problem can be solved with 1 binary search... 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 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". Thanks to svr very lot. AC!!!!
Edited by author 31.03.2012 10:44
Edited by author 31.03.2012 10:44 I tried to use 2 binary searches, but WA :( 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 :) |
| IS It possible to solve this problem by geometry? | vano_B1 | 1256. Кладбищенский сторож | 24 окт 2011 16:28 | 2 |
|
| hints | Rumter (3) | 1256. Кладбищенский сторож | 23 окт 2011 13:58 | 3 |
hints Rumter (3) 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. tests Rumter (3) 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 |
| To admins: My AC solution fails on some tests | hedrok | 1256. Кладбищенский сторож | 28 июл 2008 23:00 | 1 |
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 |
| Help... | Aleksey (BMSTU IU7) | 1256. Кладбищенский сторож | 8 авг 2006 18:08 | 2 |
Help... Aleksey (BMSTU IU7) 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?????? Not always, but as partial case - yes... |
| Help, Please! Give me some tests plz. (+) | Victor Barinov (TNU) | 1256. Кладбищенский сторож | 28 июл 2006 14:59 | 3 |
I have WA on test 3. I need godd tests. Help me please.
Thanks! Test1:
500 1000 500 250
Test2:
1000 600 600 400
Test3:
0 0 0 r |
| Is this problem equivalent to another one? | Agh | 1256. Кладбищенский сторож | 11 сен 2003 21:05 | 2 |
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 Cause the task is the same but the square where distance is zero
decreade by two. |
| I've got AC using double binary search with subsequences (-) | Dmitry 'Diman_YES' Kovalioff | 1256. Кладбищенский сторож | 21 мар 2003 18:28 | 1 |
|
| Народ!!!! | Perov Rodion | 1256. Кладбищенский сторож | 19 мар 2003 11:36 | 2 |
Слушайте ну помоему задачка-то несерьезная.
Но тока пока я ее не решил но это не важно)))))
Карроче- переходим к кординатному методу.
Ну есенно парочку условий- ну если они на одной прямой то все понятно-
если домик внутри окружности цепи тоже вроде все ок и остальное:
если цепи пересекаются то к точке пересечения и обратно
если нет то два варианта- какой из них короче сказать не могу но это
машинным способом проверить можно
Тк вот первы |
| do u know how to solve it? | nicushor | 1256. Кладбищенский сторож | 17 мар 2003 16:01 | 1 |
do u know how to solve it? i don't........ |
| do u know how to solve it? | nicushor | 1256. Кладбищенский сторож | 17 мар 2003 16:00 | 1 |
|
| i've got AC | ratrax21 | 1256. Кладбищенский сторож | 17 мар 2003 14:47 | 1 |
if you want the solution e-mail me to Daniciuc_Marian@yahoo.com |
