| Show all threads Hide all threads Show all messages Hide all messages |
| the real hint | ASK | 1719. Kill the Shaitan-Boss | 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 Shaitan-Boss | 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 Shaitan-Boss | 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 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
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 Shaitan-Boss | 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, 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. 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 Shaitan-Boss | 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 Shaitan-Boss | 23 Oct 2009 17:40 | 1 |
|
| Clarification | Alast Tiro | 1719. Kill the Shaitan-Boss | 12 Oct 2009 02:25 | 1 |
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 |
