Encuentra K puntos más cercanos al origen

Dada una lista de puntos en el plano 2-D y un número entero K. La tarea es encontrar los puntos K más cercanos al origen e imprimirlos.
Nota : La distancia entre dos puntos en un plano es la distancia euclidiana .

Ejemplos: 

Input : point = [[3, 3], [5, -1], [-2, 4]], K = 2
Output : [[3, 3], [-2, 4]]
Square of Distance of origin from this point is 
(3, 3) = 18
(5, -1) = 26
(-2, 4) = 20
So the closest two points are [3, 3], [-2, 4].

Input : point = [[1, 3], [-2, 2]], K  = 1
Output : [[-2, 2]]
Square of Distance of origin from this point is
(1, 3) = 10
(-2, 2) = 8 
So the closest point to origin is (-2, 2)

Enfoque: la idea es calcular la distancia euclidiana desde el origen para cada punto dado y ordenar la array de acuerdo con la distancia euclidiana encontrada. Imprime los primeros k puntos más cercanos de la lista.

Algoritmo: 
Considere dos puntos con coordenadas como (x1, y1) y (x2, y2) respectivamente. La distancia euclidiana entre estos dos puntos será: 

√{(x2-x1)2 + (y2-y1)2}

1. Ordene los puntos por distancia utilizando la fórmula de la distancia euclidiana.
2. Seleccione los primeros puntos K de la lista
3. Imprime los puntos obtenidos en cualquier orden.

Nota: 

• En multimap podemos almacenar directamente el valor de {(x2-x1) ² + (y2-y1) ² } en lugar de su raíz cuadrada debido a la siguiente propiedad: Si sqrt(x) < sqrt(y) the x < y
• Debido a esto, hemos reducido la complejidad del tiempo (la complejidad del tiempo de la raíz cuadrada de un número entero es O(√ n)) 

A continuación se muestra la implementación del enfoque anterior: 

// C++ program for implementation of 
// above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to print required answer
void pClosest(vector<vector<int>> pts, int k)
{
     
    // In multimap values gets
    // automatically sorted based on
    // their keys which is distance here
    multimap<int, int> mp;
    for(int i = 0; i < pts.size(); i++)
    {
        int x = pts[i][0], y = pts[i][1];
        mp.insert({(x * x) + (y * y) , i});
    }
     
    for(auto it = mp.begin();
             it != mp.end() && k > 0;
             it++, k--)
        cout << "[" << pts[it->second][0] << ", "
             << pts[it->second][1] << "]" << "\n";
}
 
// Driver code
int main()
{
    vector<vector<int>> points = { { 3, 3 },
                                   { 5, -1 },
                                   { -2, 4 } };
     
    int K = 2;
     
    pClosest(points, K);
    return 0;
}
 
// This code is contributed by sarthak_eddy.

// Java program for implementation of 
// above approach
import java.util.*;
 
class GFG{
     
// Function to print required answer
static void pClosest(int [][]pts, int k)
{
    int n = pts.length;
    int[] distance = new int[n];
    for(int i = 0; i < n; i++)
    {
        int x = pts[i][0], y = pts[i][1];
        distance[i] = (x * x) + (y * y);
    }
 
    Arrays.sort(distance);
     
    // Find the k-th distance
    int distk = distance[k - 1];
 
    // Print all distances which are
    // smaller than k-th distance
    for(int i = 0; i < n; i++)
    {
        int x = pts[i][0], y = pts[i][1];
        int dist = (x * x) + (y * y);
         
        if (dist <= distk)
            System.out.println("[" + x + ", " + y + "]");
    }
}
 
// Driver code
public static void main (String[] args)
{
    int points[][] = { { 3, 3 },
                       { 5, -1 },
                       { -2, 4 } };
 
    int K = 2;
     
    pClosest(points, K);
}
}
 
// This code is contributed by sarthak_eddy.

# Python3 program for implementation of
# above approach
 
# Function to return required answer
def pClosest(points, K):
 
    points.sort(key = lambda K: K[0]**2 + K[1]**2)
 
    return points[:K]
 
# Driver program
points = [[3, 3], [5, -1], [-2, 4]]
 
K = 2
 
print(pClosest(points, K))

// C# program for implementation
// of above approach
using System;
class GFG{
     
// Function to print
// required answer
static void pClosest(int [,]pts,
                     int k)
{
  int n = pts.GetLength(0);
 
  int[] distance = new int[n];
   
  for(int i = 0; i < n; i++)
  {
    int x = pts[i, 0],
        y = pts[i, 1];
    distance[i] = (x * x) +
                  (y * y);
  }
 
  Array.Sort(distance);
 
  // Find the k-th distance
  int distk = distance[k - 1];
 
  // Print all distances which are
  // smaller than k-th distance
  for(int i = 0; i < n; i++)
  {
    int x = pts[i, 0],
        y = pts[i, 1];
    int dist = (x * x) +
               (y * y);
 
    if (dist <= distk)
      Console.WriteLine("[" + x +
                        ", " + y + "]");
  }
}
 
// Driver code
public static void Main (string[] args)
{
  int [,]points = {{3, 3},
                   {5, -1},
                   {-2, 4}};
  int K = 2;
  pClosest(points, K);
}
}
 
// This code is contributed by Chitranayal

<script>
// Javascript program for implementation of
// above approach
 
// Function to print required answer
function pClosest(pts,k)
{
    let n = pts.length;
    let distance = new Array(n);
    for(let i = 0; i < n; i++)
    {
        let x = pts[i][0], y = pts[i][1];
        distance[i] = (x * x) + (y * y);
    }
  
    distance.sort(function(a,b){return a-b;});
      
    // Find the k-th distance
    let distk = distance[k - 1];
  
    // Print all distances which are
    // smaller than k-th distance
    for(let i = 0; i < n; i++)
    {
        let x = pts[i][0], y = pts[i][1];
        let dist = (x * x) + (y * y);
          
        if (dist <= distk)
            document.write("[" + x + ", " + y + "]<br>");
    }
}
 
// Driver code
let points = [[3, 3], [5, -1], [-2, 4]];
let K = 2;
pClosest(points, K);
      
// This code is contributed by rag2127
</script>

[[3, 3], [-2, 4]]

Análisis de Complejidad: 

• Complejidad temporal: O(n log n). 
  La complejidad del tiempo para encontrar la distancia desde el origen para cada punto es O(n) y para ordenar la array es O(n log n)
• Complejidad espacial: O(n). 
  Como estamos haciendo una array para almacenar la distancia desde el origen para cada punto.