Page 1 of 3

10566 - Crossed Ladders

Posted: Thu Oct 09, 2003 1:13 am
by BiK
I thought that I have good background Mathematics and that this should be an easy problem in Geometry. Just the opposite, this proved wrong. I'm totally stumped. Please help me to solve the problem.

Posted: Thu Oct 09, 2003 2:52 am
by Larry
binary search.

Posted: Thu Oct 09, 2003 5:39 am
by titid_gede
binary search? what is the relationship between this problem and binary seach? isnt it totally math? please give me enlightment.. :) :) :)
i havent solved this problem, and i'm very weak in math.
thanks before...

Posted: Thu Oct 09, 2003 6:47 am
by sharklu2000
It means that you continues trying the middle of the large number and the small number until you get the root.

Posted: Thu Oct 09, 2003 11:29 am
by Observer
This method is usually referred to as "bisection method".

Posted: Thu Oct 09, 2003 12:22 pm
by Farid Ahmadov
Hi. I don't think that I am weak in math. But I don't understand why I am wrong?

I found a formula and can prove it.
Do you see the picture below?

Image

It is my prove. Isn't it right and why?
Thanx.

Posted: Thu Oct 09, 2003 2:43 pm
by Observer
Plz ignore me. :D

Posted: Thu Oct 09, 2003 5:10 pm
by BiK
2Farid:

How do you get r/c = z*z?

Posted: Thu Oct 09, 2003 5:37 pm
by hewei
Hi, Farid Ahmadov!
There was a fault in your proof:
From 6th line: a/b = a1/b1 = z
To 7th line: r/c = c/r1/ = z*z

The process 6th -> 7th requires the angle you noted in the graph to be right, i.e. 90 degrees.

That's why the formula is even not suitable for the sample, isn't it?

Posted: Thu Oct 09, 2003 8:54 pm
by Farid Ahmadov
Sorry. I am not correct. My mind was somewhere near 90 degrees.
Only 7th formula is not correct. r/c = c/r1 = z*z*d
d = sin(90+alfa+beta). I have to find what it is.

Posted: Thu Oct 09, 2003 10:37 pm
by BiK
Thanks to all. After all finding an equation and solving it through binary search was enough. However a mathematician always tries to find some nice looking formula which maybe is not possible in this problem (our mistake).

Posted: Fri Oct 10, 2003 4:05 pm
by Farid Ahmadov
Hi BiK. You are right. I know how to solve it with binary search. But I want to solve it matematically. And it is possible because l depends on only x,y and c. I just have to find dependence between them.

Posted: Sat Oct 11, 2003 3:45 am
by hewei
Well, as far as I see, to find a nice formula is as difficult as to solve the equation below:

(when x is not equal to y)
(x*x - l*l) * sqrt(y*y - l*l) - (y*y - l*l) * sqrt(x*x - l*l) = c*(x*x - y*y)

but, when x equals y, the problem becomes obviously trivial:
l = sqrt(x*x - 4*c*c)

help:wrong answer

Posted: Sun Oct 12, 2003 9:14 am
by fqsxr
I've found an idea:
solve sqrt(x^2-l^2)*sqrt(y^2-l^2)/(sqrt(x^2-l^2)+sqrt(y^2-l^2))-c=0
and I've written an program for solving this
but the online judge told me wrong answer
Who can tell me how to debug this? Can I see the test datas?

Posted: Sun Oct 12, 2003 9:34 pm
by marian
Mathematical solution to this problem can be found here: http://mathworld.wolfram.com/CrossedLaddersProblem.html