| ENG RUS | Timus Online Judge |
Обсуждение задачи 1719. Убей Шайтан-боссаASK the real hint // Задача 1719. Убей Шайтан-босса 19 апр 2018 22:23 To find the shortest path from point O to lines AB and CD (in that order) one needs to consider three possibilities, namely projection from O to CD (if it intersects AB); projection on CD of the reflection of O thru AB (if it intersects AB); intersection of AB and CD. xurshid_n hint // Задача 1719. Убей Шайтан-босса 15 май 2012 14:20 has simple geometrical solution!!! try rotate perpendikulayr with 'theta' angle, and find optimal 'theta'. This 'theta' angle equal angle of two lines!!!!!! Tashkent IAC Please somebody give some tests! [7] // Задача 1719. Убей Шайтан-босса 26 окт 2009 16:24 I always get WA 2...., and I don't know why...... svr Re: Please somebody give some tests! [6] // Задача 1719. Убей Шайтан-босса 27 окт 2009 15:39 My program is full search(rather primitive) but got Ac. Next tests also simple: 1 1 2 2 1 -3 2 -6 0.00000000 5 5 10 5 -1 -4 -3 -4 1.581139 -100 1 -200 1 -100 2 -200 2 2.0000000 -1 0 1 -2 -2 0 3 -10 0.485071 Edited by author 27.10.2009 15:49 Tashkent IAC Re: Please somebody give some tests! [5] // Задача 1719. Убей Шайтан-босса 27 окт 2009 16:39 Could you tell me how you get 2-nd answer(1.581139) Is it a distance from starting point to the lines intersrction? If it is, could you give me the coordinates of lines intersection? P.S. I got 1.597191412 svr Re: Please somebody give some tests! [4] // Задача 1719. Убей Шайтан-босса 27 окт 2009 19:59 I depend on obviouse statement: optimal path is some segment from (0,0) to one of lines and projection to another one. So I make full search about this situation. You think about line inersection as one of solutions of variational equation. But there are many other solutions. Tashkent IAC Re: Please somebody give some tests! [3] // Задача 1719. Убей Шайтан-босса 27 окт 2009 20:24 In my solution I also try this kind of optimal path, but I couldn't get your answer 1.581139 ..... svr Re: Please somebody give some tests! [2] // Задача 1719. Убей Шайтан-босса 27 окт 2009 20:37 It is simple. Soon I will give to this issue two points: A2 abd A3( A1=(0,0)) and this will be best help. svr Re: Please somebody give some tests! [1] // Задача 1719. Убей Шайтан-босса 28 окт 2009 08:58 5 5 10 5 -1 -4 -3 -4 1.581139 Intersection (0.7142857,-1.4285714). First move to (0.84995501, -1.22506748) (Too far going to intersection, we are crossing angle.) Edited by author 28.10.2009 09:10 bsu.mmf.team Re: Please somebody give some tests! // Задача 1719. Убей Шайтан-босса 31 окт 2009 03:11 How did you calculate the point of first move? I got 1.5811388 too, but first point is (0.849057,-1.22642), which lies on a line p:=((5,5),(-1,-4)). I searched such points with a help of finding a conditional extremal value of a function: F(x,y):=Dist((0,0),point)+Dist(point,q) (q is the second line), where point lies on p, and a function G(x,y):=Dist((0,0),point)+Dist(point,p), where point lies on q. But I still have WA#3((( I don't know any reason. Edited by author 31.10.2009 03:13 Edited by author 31.10.2009 04:07 vgu Why WA31? [7] // Задача 1719. Убей Шайтан-босса 24 окт 2009 14:17 Alex Tolstov (Vologda STU) Re: Why WA31? [6] // Задача 1719. Убей Шайтан-босса 25 окт 2009 00:01 What method do you use? vgu Re: Why WA31? [5] // Задача 1719. Убей Шайтан-босса 26 окт 2009 00:55 I use ternary search. My C++ solution has wa17 and Pascal solution with extended has wa31. Maybe this because i use sqrt function? Edited by author 26.10.2009 00:56 Edited by author 26.10.2009 00:56 Alex Tolstov (Vologda STU) Re: Why WA31? [4] // Задача 1719. Убей Шайтан-босса 26 окт 2009 16:29 I use ternary search too, sqrt-function, and type double in Java. I don't use epsilon in calculations. May be, calculations the distance from point to line is not too exact? I use vector product to calc 2*area of a triangle, and then divide it on base to get distance. vgu Re: Why WA31? [3] // Задача 1719. Убей Шайтан-босса 26 окт 2009 18:48 I use vector product too :( why wa31 :( Alex Tolstov (Vologda STU) Re: Why WA31? // Задача 1719. Убей Шайтан-босса 26 окт 2009 19:03 send me your code, and I'll try to tell you where is your bug: gm.alext@gmail.com :) Alex Tolstov (Vologda STU) Re: Why WA31? [1] // Задача 1719. Убей Шайтан-босса 27 окт 2009 23:34 I am sure that you have problem with precision. I tested one of solutions and found that point coordinates on line must be very exact. One way to get very exact coordinates: we have two points: a and b. double factor = value in range from -10000 to 10000 double dx = b.x - a.x; double dy = b.y - a.y; double x = a.x + dx * factor; double y = a.y + dy * factor; (x, y) - coordinates of point belongs to line, containing a and b. vgu Re: Why WA31? // Задача 1719. Убей Шайтан-босса 28 окт 2009 16:07 AC now :) Great thanks to Alex Tolstov Alexander Samal Crossing of diagonals? [3] // Задача 1719. Убей Шайтан-босса 11 окт 2009 00:10 unlucky [Vologda SPU] Re: Crossing of diagonals? [2] // Задача 1719. Убей Шайтан-босса 27 окт 2009 20:24 No! WA 2 But it is strange... Alex Tolstov (Vologda STU) Re: Crossing of diagonals? [1] // Задача 1719. Убей Шайтан-босса 27 окт 2009 21:28 Not strange. Your idea is a drivel!! unlucky [Vologda SPU] Re: Crossing of diagonals? // Задача 1719. Убей Шайтан-босса 28 окт 2009 13:23 Yep. ahmedov(NUUz_2) Why WA2?Please, give me some tests. // Задача 1719. Убей Шайтан-босса 23 окт 2009 17:40 Alast Tiro Clarification // Задача 1719. Убей Шайтан-босса 12 окт 2009 02:25 Shaitan-pipe kill ALL bosses on the line. If you have WA#6 try this test: 100 0 -100 0 0 1000 0 100 Correct answer is not 100.0000000000
|