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

lightoj-1062(crossed ladders)
Автор restart., 9 лет назад, По-английски

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
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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
    → Ответить