def rotate(a,b,c)
  (b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0])
end
def qsort(start,a,p)             # 2. Упорядкування даних точок
  if (p.length<2)                # якщо масив порожній або одноелементний,
    return p                     # тобто немає що упорядковувати, … 
  end   
    k = rand(p.length)           # випадковим чином вибрати значення елемента
                                 # масиву, щоб уникнути переповнення стеку
                                 # при упорядкованих даних
  dk=(a[start][0]-a[p[k]][0]).abs+(a[start][1]-a[p[k]][1]).abs
  left   = []
  center = []
  right  = []
  for j in 0...p.length
    dj=(a[start][0]-a[p[j]][0]).abs+(a[start][1]-a[p[j]][1]).abs
    x = rotate(a[start],a[p[k]],a[p[j]])
    if x<0
      left.push(p[j])
    else if x>0
           right.push(p[j])
         else
           if dj>dk
             left.push(p[j])
           else if dj<dk
                  right.push(p[j])
                else
                      center.push(p[j])
                end 
           end
         end
    end
  end
  return(qsort(start,a,left) + center + qsort(start,a,right))
  # повернути масив, у якому елементи з вибраним значенням
  # розташовано на своєму місці, a ліворуч і праворуч від
  # них розташовано рекурсивно упорядковані масиви
end

def grahamscan(a)
  n = a.length           # кількість точок
  p = []
  for i in 0...n
    p.push(i)
  end
  for i in 0...n       # 1. Пошук стартової точки
    if ((a[p[i]][0] <  a[p[0]][0]) || 
       ((a[p[i]][0] == a[p[0]][0]) && (a[p[i]][1] < a[p[0]][1]))) 
           p[i], p[0] = p[0], p[i]
    end
  end 
  start=p[0]           # вилучення стартової точки з масиву
  p.delete_at(0)
  n = p.length
  p=qsort(start,a,p)   # 2. Упорядкування даних точок
  s = [start,p[0]]     #    Cтворення стеку s
  line=true            # 3. Перевірка розташування точок на одній прямій
  for i in 2...n
    line=line && (rotate(a[0],a[1],a[i])==0)  
    if (not line)
      break
    end
  end
  if (line)
    return s
  end
  
  for i in 1...n        # 4. Видалення з переліку вершин тих,
                        #    в яких внутрішній кут отриманого
                        #    много­кутника більший від розгорнутого
    while (rotate(a[s[-2]],a[s[-1]],a[p[i]])<0)
      s.pop[-1]
    end
    s.push(p[i])
  end
  return s
end
a = [[110, 66], [88,108], [88, 30], [85, 83], [60, 72],
      [53, 45], [32, 72], [39,108], [11, 58], [25,  8]]
#a = [[0, 0],  [4, 4], [8, 8],  [2, 2] ]
print grahamscan(a)