Ordenar una array de puntos por su distancia desde un punto de referencia

Dada una array arr[] que contiene N puntos y un punto de referencia P , la tarea es clasificar estos puntos según su distancia desde el punto P dado .

Ejemplos:

Entrada: arr[] = {{5, 0}, {4, 0}, {3, 0}, {2, 0}, {1, 0}}, P = (0, 0) 
Salida: (1, 0) (2, 0) (3, 0) (4, 0) (5, 0) 
Explicación: 
Distancia entre (0, 0) y (1, 0) = 1 
Distancia entre (0, 0) y (2, 0) = 2 
Distancia entre (0, 0) y (3, 0) = 3 
Distancia entre (0, 0) y (4, 0) = 4 
Distancia entre (0, 0) y (5, 0) = 5 

Por lo tanto, la array ordenada de puntos será: {(1, 0) (2, 0) (3, 0) (4, 0) (5, 0)}
Entrada: arr[] = {{5, 0}, {0, 4}, {0, 3}, {2, 0}, {1, 0}}, P = (0, 0) 
Salida: (1, 0) (2, 0) (0, 3) ( 0, 4) (5, 0) 
Explicación: 
Distancia entre (0, 0) y (1, 0) = 1 
Distancia entre (0, 0) y (2, 0) = 2 
Distancia entre (0, 0) y ( 0, 3) = 3 
Distancia entre (0, 0) y (0, 4) = 4 
Distancia entre (0, 0) y (5, 0) = 5 
Por lo tanto, la array ordenada de puntos será: {(1, 0) (2, 0) (0, 3) (0, 4) (5, 0)}

Enfoque: la idea es almacenar cada elemento a su distancia del punto P dado en un par y luego ordenar todos los elementos del vector de acuerdo con la distancia almacenada.

• Para cada uno de los puntos dados: 
  • Encuentre la distancia del punto desde el punto de referencia P fórmula a continuación:

Distance = 

• Agregar la distancia en una array
• Ordene la array de distancia e imprima los puntos según la distancia ordenada.
  • Complejidad del tiempo: como en el enfoque anterior, hay una clasificación de una array de longitud N, que toma el tiempo O (N * logN) en el peor de los casos. Por lo tanto, la Complejidad del Tiempo será O(N*log N) .
  • Complejidad del espacio auxiliar: como en el enfoque anterior, se utiliza espacio adicional para almacenar la distancia y los puntos como pares. Por lo tanto, la complejidad del espacio auxiliar será O(N) .

// C++ program
 
#include <bits/stdc++.h>
using namespace std;
 
bool compare(pair<int, pair<int, int> > a,
             pair<int, pair<int, int> > b)
{
    if (a.first == b.first) {
        return 0;
    }
    else {
        return (a.first < b.first) ? -1 : 1;
    }
}
 
// Function to sort the array of
// points by its distance from P
void sortArr(vector<vector<int> > arr, int n, vector<int> p)
{
    // Vector to store the distance
    // with respective elements
 
    vector<pair<int, pair<int, int> > > vp;
    // Storing the distance with its
    // distance in the vector array
    for (int i = 0; i < n; i++) {
 
        int dist = pow((p[0] - arr[i][0]), 2)
                   + pow((p[1] - arr[i][1]), 2);
        vp.push_back(make_pair(
            dist, make_pair(arr[i][0], arr[i][1])));
    }
 
    // Sorting the array with
    // respect to its distance
    sort(vp.begin(), vp.end(), compare);
 
    // Output
    for (int i = 0; i < n; i++) {
        cout << "(" << vp[i].second.first << ", "
             << vp[i].second.second << ") " << endl;
    }
}
 
int main()
{
    vector<vector<int> > arr
        = { { 5, 5 }, { 6, 6 }, { 1, 0 },
            { 2, 0 }, { 3, 1 }, { 1, -2 } };
    int n = 6;
    vector<int> p = { 0, 0 };
   
    // Function to perform sorting
    sortArr(arr, n, p);
}
 
// The code is contributed by Gautam goel (gautamgoel962)

<script>
// Javascript program
 
function sortFunction(a, b) {
    if (a[0] === b[0]) {
        return 0;
    }
    else {
        return (a[0] < b[0]) ? -1 : 1;
    }
}
 
// Function to sort the array of
// points by its distance from P
function sortArr(arr, n, p)
{
    // Vector to store the distance
    // with respective elements
     
    var vp = new Array(n);
    // Storing the distance with its
    // distance in the vector array
    for (var i = 0; i < n; i++) {
   
        var dist = Math.pow((p[0] - arr[i][0]), 2)
              + Math.pow((p[1] - arr[i][1]), 2);
        vp[i] = [dist, [arr[i][0], arr[i][1]]];
    }
     
    // Sorting the array with
    // respect to its distance
    vp.sort(sortFunction);
   
    // Output
    for (var i = 0; i < n; i++) {
        document.write("(" + vp[i][1][0] + ", " + vp[i][1][1] + ") ");
    }
}
 
var arr = [[ 5, 5 ], [ 6, 6 ], [ 1, 0], [ 2, 0 ], [ 3, 1 ], [ 1, -2 ]];
var n = 6;
var p = [ 0, 0 ];
// Function to perform sorting
sortArr(arr, n, p);
</script>

Producción:

(1, 0) (2, 0) (1, -2) (3, 1) (5, 5) (6, 6)