Encuentre el radio mínimo tal que al menos el punto k se encuentre dentro del círculo

Dado un entero positivo K, un círculo con centro en (0, 0) y coordenadas de algunos puntos. La tarea es encontrar el radio mínimo del círculo para que al menos k puntos se encuentren dentro del círculo. Muestra el cuadrado del radio mínimo.
 

Ejemplos:  

Input : (1, 1), (-1, -1), (1, -1), 
         k = 3
Output : 2
We need a circle of radius at least 2
to include 3 points.


Input : (1, 1), (0, 1), (1, -1), 
         k = 2
Output : 1
We need a circle of radius at least 1
to include 2 points. The circle around
(0, 0) of radius 1 would include (1, 1)
and (0, 1).

La idea es encontrar el cuadrado de la distancia euclidiana de cada punto desde el origen (0, 0). Ahora, ordena estas distancias en orden creciente. Ahora el k ^-ésimo elemento de distancia es el radio mínimo requerido.
A continuación se muestra la implementación de este enfoque: 
 

// C++ program to find minimum radius
// such that atleast k point lie inside
// the circle
#include<bits/stdc++.h>
using namespace std;
 
// Return minimum distance required so that
// atleast k point lie inside the circle.
int minRadius(int k, int x[], int y[], int n)
{
   int dis[n];
     
   // Finding distance between of each
   // point from origin
   for (int i = 0; i < n; i++)
       dis[i] = x[i] * x[i] + y[i] * y[i];
     
    // Sorting the distance
    sort(dis, dis + n);
     
    return dis[k - 1];
}
 
// Driven Program
int main()
{
  int k = 3;
  int x[] = { 1, -1, 1 };
  int y[] = { 1, -1, -1 };
  int n = sizeof(x)/sizeof(x[0]);
     
  cout << minRadius(k, x, y, n) << endl;
     
  return 0;
}

// Java program to find minimum radius
// such that atleast k point lie inside
// the circle
import java.util.Arrays;
 
class GFG
{
 
    // Return minimum distance required so that
    // atleast k point lie inside the circle.
    static int minRadius(int k, int[] x, int[] y,
                                          int n)
    {
        int[] dis=new int[n];
     
        // Finding distance between of each
        // point from origin
        for (int i = 0; i < n; i++)
            dis[i] = x[i] * x[i] + y[i] * y[i];
     
        // Sorting the distance
        Arrays.sort(dis);
     
        return dis[k - 1];
    }
 
    // Driven Program
    public static void main (String[] args) {
         
    int k = 3;
    int[] x = { 1, -1, 1 };
    int[] y = { 1, -1, -1 };
    int n = x.length;
     
    System.out.println(minRadius(k, x, y, n));
 
    }
}
 
/* This code is contributed by Mr. Somesh Awasthi */

# Python3 program to find minimum radius
# such that atleast k point lie inside
# the circle
 
 
# Return minimum distance required so
# that atleast k point lie inside the
# circle.
def minRadius(k, x, y, n):
    dis = [0] * n
 
    # Finding distance between of each
    # point from origin
 
    for i in range(0, n):
        dis[i] = x[i] * x[i] + y[i] * y[i]
 
    # Sorting the distance
    dis.sort()
 
    return dis[k - 1]
         
# Driver Program
k = 3
x = [1, -1, 1]
y = [1, -1, -1]
n = len(x)
 
print(minRadius(k, x, y, n))
 
# This code is contributed by
# Prasad Kshirsagar

// C# program to find minimum radius
// such that atleast k point lie inside
// the circle
using System;
 
class GFG {
 
    // Return minimum distance required
    // so that atleast k point lie inside
    // the circle.
    static int minRadius(int k, int []x,
                          int[] y, int n)
    {
        int[] dis = new int[n];
     
        // Finding distance between of
        // each point from origin
        for (int i = 0; i < n; i++)
            dis[i] = x[i] * x[i] +
                       y[i] * y[i];
     
        // Sorting the distance
        Array.Sort(dis);
     
        return dis[k - 1];
    }
 
    // Driven Program
    public static void Main ()
    {
        int k = 3;
        int[] x = { 1, -1, 1 };
        int[] y = { 1, -1, -1 };
        int n = x.Length;
         
        Console.WriteLine(
              minRadius(k, x, y, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find minimum radius
// such that atleast k point lie inside
// the circle
 
// Return minimum distance required
// so that atleast k point lie
// inside the circle.
function minRadius($k, $x, $y, $n)
{
    $dis =array();
         
    // Finding distance between
    // of each point from origin
    for ($i = 0; $i < $n; $i++)
        $dis[$i] = $x[$i] * $x[$i] +
                   $y[$i] * $y[$i];
         
        // Sorting the distance
        sort($dis);
         
        return $dis[$k - 1];
}
 
// Driver Code
$k = 3;
$x = array(1, -1, 1);
$y = array(1, -1, -1);
$n = count($x);
     
echo minRadius($k, $x, $y, $n) ;
     
// This code is contributed by anuj_67.
?>

<script>
// Javascript program to find minimum radius
// such that atleast k point lie inside
// the circle
 
    // Return minimum distance required so that
    // atleast k point lie inside the circle.
    function minRadius(k, x, y, n) {
     
        let dis = Array.from({length: n}, (_, i) => 0);
       
        // Finding distance between of each
        // point from origin
        for (let i = 0; i < n; i++)
            dis[i] = x[i] * x[i] + y[i] * y[i];
       
        // Sorting the distance
        dis.sort();
       
        return dis[k - 1];
    }
   
// driver function
 
    let k = 3;
    let x = [ 1, -1, 1 ];
    let y = [ 1, -1, -1 ];
    let n = x.length;
       
    document.write(minRadius(k, x, y, n));
  
 // This code is contributed by code_hunt.
</script>   

Producción: 

2

Complejidad temporal: O(n + nlogn)
Espacio auxiliar: O(n)

Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.