Московская олимпиада по информатике - 2005: различия между версиями

Содержимое удалено Содержимое добавлено
Строка 365:
2. Итак, можно считать, что искомая прямая должна проходить через какую-либо вершину. Теперь будем вращать эту прямую против часовой стрелки вокруг вершины, через которую она проходит, пока прямая не пройдет через вторую вершину. Аналогично, степень полученной прямой равна степени исходной. И теперь прямая проходит через две различных вершины.
 
На этих идеях основано решение с алгоритмической сложностью O(N<subsup>3</subsup>), где N – количество отрезков: перебираем все пары вершин; для каждой пары считаем степень прямой; через эти вершины проходящей; среди них выбираем прямую с наибольшей степенью. Но такое решение не набирает полного балла.
 
Решение с алгоритмической сложностью O(N<subsup>2</subsup> log N ) использует только первое рассуждение: искомая прямая проходит через вершину. Таким образом, если для каждой вершины найти прямую наибольшей степени, которая проходит через нее, то выбрав среди всех степеней максимум, получим ответ.
 
Научимся искать прямую с наибольшей степенью, проходящую через вершину P(xp, yp). Любое упоминание прямой теперь подразумевает, что она проходит через P. Сразу договоримся не рассматривать отрезки, проходящие через P, так как они не влияют на поиск прямой максимальной степени. Главное – не забыть их подсчитать и учесть при вычислении степени прямой.
Строка 401:
Понятно, что после просмотра вершины Q степень всех прямых между PQ и PS (где S - следующая за Q вершина в отсортированном списке) равна C (любая из этих прямых пересекает все отрезки, которые уже «начались», но еще не «закончились», их ровно C по построению). Среди всех таких значений C надо выбрать наибольшее. В качестве прямой с соответствующей степенью можно брать, к примеру, PQ, как и описано в алгоритме.
 
Сложность общего случая (когда отрезки расположены произвольно) заключается в следующем: пусть мы сравниваем точки как обычно - по полярному углу. Тогда привычное свойство сравнения «из a <= b, b <= c, следует a <= c» не выполняется, например, для вершин a = (0, 1), b = (1/2, -1/2), c = (-1/2, -1/2), P = (0, 0). Поэтому любая сортировка за время N log N, основанная на таком свойстве, будет сортировать точки неправильно. А ведь именно за счет сортировки за время N log N мы имеем оценку O(N<subsup>2</subsup> log N ), а не O(N<subsup>3</subsup>).
 
Существует несколько способов выйти из этой ситуации, но наиболее простой, на наш взгляд, следующий.