Поиск всех комбинаций элементов набора, удовлетворяющих определенному условию

Question

Вот проблема, которую я пытаюсь решить: Мне задан набор строк с наклоном m и константой c. Теперь мне нужно найти число точек пересечения этих прямых, которые пересекаются в правой части оси y. Это по существу означает, что для линий 1 и 2

    c1>c2 and m2>m1 

мне нужно алгоритм O (NlogN), который подсчитывает общее число точек пересечения на правой стороне оси у (если алгоритм существует). Я всегда могу сделать грубую силу, чтобы получить алгоритм o (n2), но я ищу более быстрый алгоритм.

Answer 1

Два сортированных вектора сделают это.

1. Нажать все линии в вектор v1.
2. Сортировка v1 по постоянной c. После этого v1 [0] - это линия с наименьшим c.
3. Обход v1 от начала до конца. Для каждого элемента e в v1 мы должны рассматривать только те элементы, которые были раньше (c1> c2). Теперь задача состоит в том, чтобы найти среди всего посещенного элемента элемент с m2> m1.
4. Таким образом, мы просто нажимаем элемент, который был посещен, в вектор v2.Мы должны держать его отсортированным по наклону m после каждой вставки (самобалансировка BST будет выполнять эту задачу). Поскольку v2 сортируется по m, бинарный поиск расскажет вам, сколько элементов удовлетворяют m2> m1.

Сортировка n log n.

Вставить в v2 log n (Это может быть достигнуто с помощью самобалансировки BST, и он будет вызывать n раз).

Двоичный поиск - log n (invoke n раз).

Так что O (Nlog п)

Если вы пишете это в C++, это будет похоже, что (я не определяю v2, потому что вы будете реализовывать себя баланс BST):

struct line 
{ 
    int c,m; 
    line(int a,int b):c(a),m(b){} 
    bool operator <(const line &a) const 
    { 
     return m>a.m; 
    } 
}; 
bool cmp(const line &v1,const line &v2) 
{ 
    return v1.c<v2.c; 
} 
int main() 
{ 
    vector<line> v1; 
    v1.push_back(line(1,3)); 
    v1.push_back(line(4,1)); 
    v1.push_back(line(3,1)); 
    v1.push_back(line(2,2)); 
    sort(v1.begin(),v1.end(),cmp); 
    int ans=0; 
    for(int i=0;i<v1.size();i++) 
    { 
     int num=v2.find(v1[i]);//return the number of element whose m is larger than v1[i]. 
     ans+=num; 
     v2.insert(v1[i]);// in every step, the element e in v2 will satisfy e.c<v1[i].c 
    } 
    cout << ans; 
} 

Это все. Если у вас есть какие-либо вопросы, оставьте мне комментарий.

Answer 2

В худшем случае для этой проблемы требуются операции O (n^2).

Предположим, что я рисую одну строку, тогда не может быть пересечений. Я могу нарисовать линию, которая пересекает эту линию в уникальной точке. Теперь я могу нарисовать линию, которая пересекает обе предыдущие строки. Я могу продолжить рисование линий, пересекающих каждую предыдущую строку.

Это означает, что число точек пересечения может достигнуть:

1 + 2 + 3 + 4 + 5 + ... + п-1

Учитывая ввод размера п линий, размер выход для этой проблемы может быть (N * (N-1))/2 точки или около N квадрата над 2.

Следовательно, даже для правильного ответа требуется O (n^2) в худшем случае.

отредактированный, игнорировать предыдущий, я думал, что вы хотите фактические точки пересечения, а не только счет.

Answer 3

Я отправляю свое решение, потому что я думаю, что это более просто реализовать:

Допустим, у вас есть объекты Line и следующие атрибуты:

- m (slope, initialized on start) 
- c (constant, initialized on start) 
- pos_m (default 0 value) 
- pos_c (default 0 value) 

Теперь у вас есть V вектор этих линий, а затем:

1. Сортировка V с помощью ключа m на элементах (O (NlogN)).
2. Iterate V, по индексу i комплект V[i].pos_m = i (O (n)).
3. Сортировка V с помощью клавиши c на элементах (O (nlogn)).
4. Iterate V, по индексу i комплект V[i].pos_c = i. (На)).
5. Пусть result = 0 Теперь итерацию по V индекса i сделать result += | V[i].pos_m - V[i].pos_c | (O (п))

На сортировке, если сравнить значение равно затем использовать другой ключ для решения заказа (если оба равны, они одна и та же линия). Например, если на 1. две линии получили один и тот же наклон, то пусть константа будет решающим.