Блог пользователя restart.

Автор restart., 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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