def rotate(a,b,c)
  return (b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0])
end
def jarvismarch(a)
  n = a.length   # 1. Пошук стартової точки      
  p = []
  for i in 0...n 
    p.push(i)
  end
  for i in 1...n
    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  
  h = [p[0]]
  line=true;   # 2. Перевірка розташування на одній прямій
  dj=(a[0][0]-a[1][0]).abs+(a[0][1]-a[1][1]).abs
  j=1
  for i in 2...n
    line=line && (rotate(a[p[0]],a[p[1]],a[p[i]])==0)
    di=(a[p[0]][0]-a[p[i]][0]).abs+(a[p[0]][1]-a[p[i]][1]).abs
    if dj<di
      j=i
      dj=di
    end
    if (not line)
      break
    end
  end
  if (line)
    h.push(p[j])
    return h
  end   
  p.delete(p[0])
  p.push(h[0])
  while true  # 3. Пошук точки, розташованої найправіше від поточної
    right = 0
    for i in 1...p.length
      if (rotate(a[h[-1]],a[p[right]],a[p[i]])<0)
        right = i
      end
    end
    if p[right]==h[0]
      break
    else
      h.push(p[right])
      p.delete(p[right])
    end
  end
  return h
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(jarvismarch(a))