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. has simple geometrical solution!!! try rotate perpendikulayr with 'theta' angle, and find optimal 'theta'. This 'theta' angle equal angle of two lines!!!!!! 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 What method do you use? 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 No! WA 2 But it is strange... Not strange. Your idea is a drivel!! 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 
