restart.'s blog

By restart., 7 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

»
7 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

  • »
    »
    7 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