restart.'s blog

lightoj-1062(crossed ladders)
By restart., 10 years ago, In English

lightoj-1062 in the category section it's showed that it can be solved by using binary search. how could i solve a geometry problem using binary search? i solved some problems using binary search. please anybody can help me what should be my strategy to solve this problem using binary search??

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use binary search for function to find answer.

I try to explain how it is.

The more will be width of a street -> the less will be height of point. Our function will be like this f(lengthofstreet) = height_of_point. Our function will be non-increasing -> so we can use binary search to find answer

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pseudocode 

    func binary_search 
|  L = 0, R = max(x, y)
|  while (R - L > EPS) // EPS is really small number like 0.000000001
|  |  M = (L + R) / 2
|  |  if(f(M) > c)
|  |  |  R = M
|  |  else 
|  |  |  L = M
|  return L
    → Reply