ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1719. Kill the Shaitan-Boss

Posted by Tashkent IAC 26 Oct 2009 16:24
I always get WA 2...., and I don't know why......
Re: Please somebody give some tests!
Posted by svr 27 Oct 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
Re: Please somebody give some tests!
Posted by Tashkent IAC 27 Oct 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
Re: Please somebody give some tests!
Posted by svr 27 Oct 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.
You think about line inersection as one of
solutions of variational equation.
But there are many other solutions.
Re: Please somebody give some tests!
Posted by Tashkent IAC 27 Oct 2009 20:24
In my solution I also try this kind of optimal path, but I couldn't get your answer 1.581139 .....
Re: Please somebody give some tests!
Posted by svr 27 Oct 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.
Re: Please somebody give some tests!
Posted by svr 28 Oct 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
Re: Please somebody give some tests!
Posted by bsu.mmf.team 31 Oct 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