Quello che stai chiedendo è equivalente a trovare il numero di non inversioni nell'array degli y s che otterrai quando si ordinano i punti rispetto a x. Puoi permetterti questo ordinamento - è O(n log n).
Vi ricordo che l'inversione è i>j e a[i] < a[j]. L'equivalenza di cui sto parlando è facile da dimostrare.
Immagina di avere 6 punti (4, 4), (2, 1), (6, 6), (3, 3), (5, 2), (1, 5). Dopo averli ordinati in relazione a x, ottieni: (1, 5), (2, 1), (3, 3), (4, 4), (5, 2), (6, 6). Puoi vedere che le pendenze negative sono formate da < (2, 1), (3, 3)>, < (2, 1), (4, 4)>, < (2, 1), (5, 2) >, < (2, 1), (6, 6)> ecc. Tutte le coppie i cui y s non sono in inversione.
Il numero di inversioni può essere conteggiato in O(n log n) utilizzando l'aumento dell'algoritmo di merge sort: in pratica è sufficiente aumentare il contatore di inversioni ogni volta che si sceglie di aggiungere il valore del sottoarray di destra (quello contenente indici più grandi). Aumenta il numero di inversioni con la quantità di valori ancora non elaborati dal subarray di sinistra.
Ecco un esempio del conteggio del numero di inversioni.
Initial array 5 1 3 4 2 6 inv := 0 // Total inversions: 6
merge step 1: <5 1 3> <4 2 6> inv = 0
merge step 2: <5> <1 3> | <4> <2 6> inv = 0
merge step 3: <5> [<1> <3>] | <4> [<2> <6>] inv = 0
merge step 4: <5> <1 3> | <4> <2 6> inv = 0 // both pairs were already sorted
merge step 5: <1 3 5> | <2 4 6> inv = 3 // we add one for 1, 3 and 2
merge step 6 <1 2 3 4 5 6> inv = 6 // we add 2 (3 and 5) for 2 and 1 for 4
Dopo aver trovato il numero di inversioni del numero di non inversioni nel numero totale di coppie (n * (n - 1))/2 meno il numero di inversioni inv.
Nel caso di esempio: 6 * 5/2 - 6 = 9.
Come è possibile trovare tutte le coppie di punti O (n^2) nel tempo O (n logn)? –
È possibile trovare il conteggio? – ashudeep21
Come dici O (n logn) è quello che stai cercando, voglio essere sicuro che una cosa sono in ordine in qualche modo ?? – MissingNumber