Как построить выпуклую оболочку алгоритмом Эндрю (monotone chain) за O(n log n)?
Нужна выпуклая оболочка набора точек. Слышал про алгоритм Эндрю с сортировкой и построением верхней и нижней цепи. Можете дать корректную целочисленную реализацию и объяснить, почему получается O(n log n) и как обрабатывать точки на рёбрах?