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

Автор dyussenaliyev, 14 лет назад, По-русски

Параметры:

Каждая из N точек становятся известны по одной точке за раз. После получения сведений об очередной точке строится выпуклая оболочка тех точек, о которых стало известно к настоящему моменту. Очевидно, можно было бы применять сканирование по Грэхему к каждой из точек, затратив при этом полное время, равное O(N^2*logN). Подскажите, как решить за О(N^2)?

Заранее спасибо.

Upd: Проблема решена. Всем спасибо!

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

14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Ну если внимательно посмотреть на алгоритм Грехема, можно заметить что за nlog только сортировка работает. Чтобы добавить одну точку в уже отсортированное множество, можно не пересортировывать все точки, а просто вставить точку в нужное место за O(n)
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Если за квадрат, то просто при добавлении очередной точки надо найти две касательные от этой точки до существующей оболочки, и заменить те ее вершины которые лежат между касательными на новую. Предварительно конечно нужно проверить не лежит ли точка внутри или на границе.

Можно добавление точки и за логарифм делать, но это сложнее.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо!