Recherche de toutes les combinaisons d'éléments d'un ensemble satisfaisant à une condition spécifique

Question

Voici un problème que j'essaie de résoudre : On me donne un ensemble de droites ayant une pente m et une constante c. Je dois maintenant trouver le nombre de points d'intersection de ces droites qui se croisent sur le côté droit de l'axe des y. Cela implique essentiellement que pour les lignes 1 et 2

                    c1>c2 and m2>m1

J'ai besoin d'un algorithme O(nlogn) qui compte le nombre total de points d'intersection sur le côté droit de l'axe des y (si l'algorithme existe). Je peux toujours utiliser la force brute pour obtenir un algorithme o(n2), mais je cherche un algorithme plus rapide.

Answer 1

Deux vecteurs triés feront l'affaire.

1. Pousser toutes les lignes dans le vecteur v1.
2. Trier v1 par la constante c. Après cela, v1[0] est la ligne avec le plus petit c.
3. Traversée v1 du début à la fin. Pour chaque élément e dans v1, nous ne devons considérer que l'élément visité avant (c1>c2). Il s'agit maintenant de trouver parmi tous les éléments visités, l'élément avec m2 > m1.
4. Il suffit donc de placer les éléments qui ont été visités dans un vecteur v2, qu'il convient de trier par la pente m après chaque insertion (le BST auto-équilibré se charge de cette tâche). Puisque v2 est trié par m, une recherche binaire vous dira combien d'éléments satisfont m2>m1.

Le tri est n log n.

L'insertion à v2 est log n (elle peut être réalisée avec le BST auto-équilibré, et il sera invoqué n fois).

La recherche binaire est log n(invoquer n fois).

C'est donc O(nlog n)

Si vous écrivez cela en C++, ce sera comme cela( Je ne définis pas la v2, parce que vous allez mettre en œuvre une BST auto-équilibrée. ):

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;
}

C'est tout. Si vous avez des questions, laissez-moi un commentaire.

Answer 2

Je publie ma solution parce que je pense qu'elle est plus simple à mettre en œuvre :

Supposons que vous ayez des objets de type Ligne et que les attributs suivants soient définis :

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

Maintenant, vous avez un V vecteur de ces lignes, donc :

1. Trier V en utilisant la touche m sur les éléments (O(nlogn)).
2. Itérer V , sur l'index i fixer V[i].pos_m = i (O(n)).
3. Trier V en utilisant la touche c sur les éléments (O(nlogn)).
4. Itérer V , sur l'index i fixer V[i].pos_c = i . (O(n)).
5. Sea result = 0 itère maintenant sur V index i do result += | V[i].pos_m - V[i].pos_c | (O(n))

Lors du tri, si la valeur comparée est égale, l'autre clé est utilisée pour décider de l'ordre (si les deux sont égales, il s'agit de la même ligne). Par exemple, si en 1. deux lignes ont la même pente, c'est la constante qui décide.

Answer 3

Dans le pire des cas, ce problème nécessite O(n^2) opérations.

Supposons que je trace une seule ligne, il ne peut y avoir d'intersection. Je peux tracer une ligne qui coupe cette ligne en un point unique. Je peux maintenant tracer une ligne qui coupe les deux lignes précédentes. Je peux continuer à tracer des lignes qui coupent toutes les lignes précédentes.

Cela signifie que le nombre de points d'intersection peut atteindre :

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

Compte tenu d'une entrée de taille n lignes, la taille de la sortie de ce problème pourrait être de (N*(N-1))/2 points ou environ N au carré sur 2.

Par conséquent, le simple fait d'afficher la bonne réponse nécessite O( n^2 ) dans le pire des cas.

édité, ignorez le précédent, je pensais que vous vouliez les points d'intersection réels, et pas seulement le nombre.