Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
binary search.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
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...
Kalo mau kaya, buat apa sekolah?

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China
It means that you continues trying the middle of the large number and the small number until you get the root.
Aspire to AC.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
This method is usually referred to as "bisection method".
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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?

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Plz ignore me.
Last edited by Observer on Fri Oct 10, 2003 5:14 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
2Farid:

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

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China
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?

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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.
_____________
NO sigNature

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
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).

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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.
_____________
NO sigNature

hewei
New poster
Posts: 14
Joined: Tue Jul 15, 2003 4:26 pm
Location: China
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)

fqsxr
New poster
Posts: 1
Joined: Sun Oct 12, 2003 9:08 am

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?

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
Mathematical solution to this problem can be found here: http://mathworld.wolfram.com/CrossedLaddersProblem.html