Количество точек над линией

Question

Рассмотрим некоторые точки на 2d плоскости и функцию f(x)=ax, где b=0. Скажем, точка - квадрат 1х1.

Теперь мы хотим сказать, сколько точек находится между функцией f(x) и линией y, как показано на рисунке ниже.

Черные точки действительны, белые нет. Мы также говорим, что точка верна, если она:

• пересекается с осью y;
• или с функцией f(x);
• или находится между ними.

Как обозначено на картинке:

Как мы можем решить эту проблему, предполагая, что мы не удаляем ни одну из точек и не добавляем их? Есть ли другой подход, кроме стандартной грубой силы?

Answer 1

Если я правильно понимаю это, точки случайны и даны вам по их координатам, а линия также дана вам.Если это так, то не может быть никаких априорных знаний о каких-либо отношениях между точками, поэтому вам нужно будет просмотреть их в указанном порядке и сравнить их координату x с 0 и координату y с f (x).).Если точка проходит проверку, вы увеличиваете счетчик, иначе - нет.Алгоритм работает за O (n) времени, и я очень сомневаюсь, что вы можете сделать что-то лучше, чем без немного дополнительной информации о точках.

Answer 2

Вопрос довольно неясен, но он следует из комментария: «Я имею в виду, что у a в f (x) = ax есть максимально допустимые точки, а их количество не превышает некоторого значения X», которое вы хотите найти a такое, что N(a)=X, где под N(a) я подразумеваю количество точек справа от оси y и над линией y=ax; или, если таких a не существует, найдите a, для которых m = N(a)<X и N(b)<m означают N(b)<X.

Вот алгоритм O (n * ln (n)): Для каждой точки p, исключая любые p ниже y=0, вычислите наклон M_p как отношение p 'sy и x координат или DBL_MAX если х = 0. Сортируйте M в порядке возрастания (это шаг O (n * ln (n))) и вызовите отсортированный массив S.

Теперь мы настроим массив T таким образом, чтобы при задании любого X, S[T[X-1]] - это наклон, который поместит точки X на или выше этого наклона:

   S[n] = DBL_MAX;
   for (k=0, j=n-1; k<=n; --j) {
      T[j] = k;
      do ++k; while (S[k]==S[k-1] && k<=n);
   }

После этого пусть будет дан любой X. Пусть h = T[X-1]. Если h<n, то N(S[h]) <= X; если h==n, на оси Y есть несколько точек, и конечный наклон работать не будет.

Этот алгоритм использует время O (n * ln (n)) и пространство O (n) для предварительной обработки набора из n точек первого квадранта, а затем использует время O (1), чтобы найти a для любого заданного X, 0 < X <= n, такой, что N(a) = X, если такой a существует, иначе возвращает a такой, что N(a) < X < N(b), если b>a, иначе возвращает DBL_MAX.