Show all threads Hide all threads Show all messages Hide all messages 
the real hint  ASK  1719. Kill the ShaitanBoss  19 Apr 2018 22:23  1 
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. 
hint  xurshid_n  1719. Kill the ShaitanBoss  15 May 2012 14:20  1 
hint xurshid_n 15 May 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!!!!!! 
Please somebody give some tests!  Tashkent IAC  1719. Kill the ShaitanBoss  31 Oct 2009 03:11  8 
I always get WA 2...., and I don't know why...... 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 Could you tell me how you get 2nd 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
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. In my solution I also try this kind of optimal path, but I couldn't get your answer 1.581139 ..... It is simple. Soon I will give to this issue two points: A2 abd A3( A1=(0,0)) and this will be best help. 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 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 
Why WA31?  vgu  1719. Kill the ShaitanBoss  28 Oct 2009 16:07  8 
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 I use ternary search too, sqrtfunction, 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. I use vector product too :( why wa31 :( send me your code, and I'll try to tell you where is your bug: gm.alext@gmail.com :) 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. AC now :) Great thanks to Alex Tolstov 
Crossing of diagonals?  Alexander Samal  1719. Kill the ShaitanBoss  28 Oct 2009 13:23  4 
No! WA 2 But it is strange... Not strange. Your idea is a drivel!! 
Why WA2?Please, give me some tests.  ahmedov(NUUz_2)  1719. Kill the ShaitanBoss  23 Oct 2009 17:40  1 

Clarification  Alast Tiro  1719. Kill the ShaitanBoss  12 Oct 2009 02:25  1 
Shaitanpipe 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 