Dados N puntos en un plano infinito 2D , donde cada punto representa el centro de un círculo que inicialmente tiene un radio de 0 que se expande a una velocidad constante de 1 unidad por segundo, la tarea es encontrar el tiempo mínimo en el que al menos K circulan superposición en un punto.
Ejemplo:
Entrada: puntos[] = {{8, 5}, {0, 4}, {3, 6}}, K = 3
Salida: 5
Explicación: Considere la cuadrícula infinita como se muestra en la imagen a continuación. la imagen muestra el estado de los círculos después de 5 segundos. Cada uno de los tres círculos se superpone y todos los puntos de la región resaltada en amarillo tienen al menos 3 círculos superpuestos. Por lo tanto, después de 5 segundos, existe un punto en el plano (es decir, (5, 4)) tal que al menos 3 círculos se superponen y es el mínimo tiempo posible.
Entrada: puntos[] = {{0, 0}, {1, 1}, {2, 2}}, K = 2
Salida: 1
Enfoque: El problema dado
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
struct coord {
long double x, y;
};
// Function to find the square of the
// distance between two given points
long double distance(coord a, coord b)
{
// Distance Formulae
return (a.x - b.x) * (a.x - b.x)
+ (a.y - b.y) * (a.y - b.y);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
bool check(vector<coord> points, int k,
long double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
// Stores the coordinates
// of 1st circle
coord C1 = points[i];
// Stores the coordinates
// of 2nd circle
coord C2 = points[j];
// Calculating dist and h
// as discussed in approach
long double dist = distance(C1, C2);
long double h
= sqrt((4 * mid - dist)
/ dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
coord P1, P2;
// By help of formulaes given above
P1.x = ((C1.x + C2.x)
+ h * (C1.y - C2.y))
/ 2;
P1.y = ((C1.y + C2.y)
+ h * (C2.x - C1.x))
/ 2;
P2.x = ((C1.x + C2.x)
- h * (C1.y - C2.y))
/ 2;
P2.y = ((C1.y + C2.y)
+ h * (C2.x - C1.x))
/ 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0, cnt2 = 0;
// Loop to traverse over all the circles
for (int k = 0; k < points.size(); k++) {
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid
<= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid
<= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k) {
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
int binSearchOnRad(vector<coord>& points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = 1e6;
// Loop to perform binary search
while (start <= end) {
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid)) {
end = mid - 1;
}
// If the required point
// does not exist
else {
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
int main()
{
vector<coord> points = { { 8, 5 },
{ 0, 4 },
{ 3, 6 } };
int K = 3;
cout << binSearchOnRad(points, K);
return 0;
}
Java
// Java implementation for the above approach
import java.io.*;
class GFG{
// Function to find the square of the
// distance between two given points
static double distance(double[] a, double[] b)
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0]) +
(a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
static boolean check(double[][] points, int k,
double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for(int i = 0; i < points.length; i++)
{
for(int j = i + 1; j < points.length; j++)
{
// Stores the coordinates
// of 1st circle
double[] C1 = points[i];
// Stores the coordinates
// of 2nd circle
double[] C2 = points[j];
// Calculating dist and h
// as discussed in approach
double dist = distance(C1, C2);
double h = Math.sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
double[] P1 = new double[2];
double[] P2 = new double[2];
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0]) +
h * (C1[1] - C2[1])) / 2;
P1[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
P2[0] = ((C1[0] + C2[0]) -
h * (C1[1] - C2[1])) / 2;
P2[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0;
int cnt2 = 0;
// Loop to traverse over all the circles
for(k = 0; k < points.length; k++)
{
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k)
{
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
static int binSearchOnRad(double[][] points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = (int)1e6;
// Loop to perform binary search
while (start <= end)
{
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid))
{
end = mid - 1;
}
// If the required point
// does not exist
else
{
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
public static void main(String[] args)
{
double[][] points = { { 8, 5 }, { 0, 4 }, { 3, 6 } };
int K = 3;
System.out.println(binSearchOnRad(points, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation of the above approach # Function to find the square of the # distance between two given points def distance(a, b): # Distance Formulae return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) # Function to check if there exist a # point having K overlapping circles with # the radius of each circle as mid def check(points, k, mid): # Squaring the value of mid # for simplicity of calculation mid *= mid for i in range(len(points)): for j in range(i + 1, len(points)): # Stores the coordinates # of 1st circle C1 = points[i] # Stores the coordinates # of 2nd circle C2 = points[j] # Calculating dist and h # as discussed in approach dist = distance(C1, C2) h = ((4 * mid - dist) / dist) ** (1 / 2) # If Circles do not intersect if (dist > 4 * mid): continue # Stores two intersection points P1 = [0] * 2 P2 = [0] * 2 # By help of formulaes given above P1[0] = ((C1[0] + C2[0]) + h * (C1[1] - C2[1])) // 2 P1[1] = ((C1[1] + C2[1]) + h * (C2[0] - C1[0])) // 2 P2[0] = ((C1[0] + C2[0]) - h * (C1[1] - C2[1])) // 2 P2[1] = ((C1[1] + C2[1]) + h * (C2[0] - C1[0])) // 2 # Stores count of overlapping # circles over P1 and P2 cnt1 = 0 cnt2 = 0 # Loop to traverse over all the circles for k in range(len(points)): # If P1 lies inside Kth circle if (distance(P1, points[k]) - mid <= 0.000001): cnt1 += 1 # If P2 lies inside Kth circle if (distance(P2, points[k]) - mid <= 0.000001): cnt2 += 1 # If count of overlapping circles # is more than K if (cnt1 >= k or cnt2 >= k): return True # If no valid point is found return False # Function to perform the binary # search over the radius of the # circles in the range [0, ∞] def binSearchOnRad(points, k): # Stores the start and end of # range of the binary search start = 0 end = 1000000 # Loop to perform binary search while (start <= end): # Stores the mid if the # current range mid = start + (end - start) // 2 # If there exist a point having # k overlapping circles with the # radius of circles as mid if (check(points, k, mid)): end = mid - 1 # If the required point # does not exist else: start = mid + 1 # Return Answer return start # Driver Code points = [[8, 5], [0, 4], [3, 6]] K = 3 print(binSearchOnRad(points, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# implementation for the above approach
using System;
class GFG {
// Function to find the square of the
// distance between two given points
static double distance(double[] a, double[] b)
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0])
+ (a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
static bool check(double[, ] points, int k, double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for (int i = 0; i < points.GetLength(0); i++) {
for (int j = i + 1; j < points.GetLength(0);
j++) {
// Stores the coordinates
// of 1st circle
double[] C1
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
C1[x] = points[i, x];
// Stores the coordinates
// of 2nd circle
double[] C2
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
C2[x] = points[j, x];
// Calculating dist and h
// as discussed in approach
double dist = distance(C1, C2);
double h
= Math.Sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
double[] P1 = new double[2];
double[] P2 = new double[2];
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0])
+ h * (C1[1] - C2[1]))
/ 2;
P1[1] = ((C1[1] + C2[1])
+ h * (C2[0] - C1[0]))
/ 2;
P2[0] = ((C1[0] + C2[0])
- h * (C1[1] - C2[1]))
/ 2;
P2[1] = ((C1[1] + C2[1])
+ h * (C2[0] - C1[0]))
/ 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0;
int cnt2 = 0;
// Loop to traverse over all the circles
for (k = 0; k < points.GetLength(0); k++) {
double[] P
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
P[x] = points[k, x];
// If P1 lies inside Kth circle
if (distance(P1, P) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, P) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k) {
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
static int binSearchOnRad(double[, ] points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = (int)1e6;
// Loop to perform binary search
while (start <= end) {
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid)) {
end = mid - 1;
}
// If the required point
// does not exist
else {
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
public static void Main(string[] args)
{
double[, ] points
= { { 8, 5 }, { 0, 4 }, { 3, 6 } };
int K = 3;
Console.WriteLine(binSearchOnRad(points, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript implementation of the above approach
// Function to find the square of the
// distance between two given points
const distance = (a, b) =>
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0]) +
(a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
const check = (points, k, mid) =>
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for(let i = 0; i < points.length; i++)
{
for(let j = i + 1; j < points.length; j++)
{
// Stores the coordinates
// of 1st circle
let C1 = points[i];
// Stores the coordinates
// of 2nd circle
let C2 = points[j];
// Calculating dist and h
// as discussed in approach
let dist = distance(C1, C2);
let h = Math.sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
let P1 = new Array(2).fill(0),
P2 = new Array(2).fill(0);
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0]) +
h * (C1[1] - C2[1])) / 2;
P1[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
P2.x = ((C1[0] + C2[0]) -
h * (C1[1] - C2[1])) / 2;
P2.y = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
// Stores count of overlapping
// circles over P1 and P2
let cnt1 = 0, cnt2 = 0;
// Loop to traverse over all the circles
for(let k = 0; k < points.length; k++)
{
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k)
{
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
const binSearchOnRad = (points, k) =>
{
// Stores the start and end of
// range of the binary search
let start = 0, end = 1000000;
// Loop to perform binary search
while (start <= end)
{
// Stores the mid if the
// current range
let mid = start + parseInt((end - start) / 2);
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid))
{
end = mid - 1;
}
// If the required point
// does not exist
else
{
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
let points = [ [ 8, 5 ], [ 0, 4 ], [ 3, 6 ] ];
let K = 3;
document.write(binSearchOnRad(points, K));
// This code is contributed by rakeshsahni
</script>
se puede resolver con la ayuda de la búsqueda binaria utilizando las siguientes observaciones:
- En cualquier momento dado t , el radio de todos los círculos debe ser t . Por lo tanto, el problema se puede convertir en encontrar el radio más pequeño tal que al menos K círculos se superpongan en un punto dado.
- El radio requerido más pequeño se puede calcular realizando una búsqueda binaria sobre él en el rango [0, ∞] .
Ahora, la tarea requerida es verificar para un radio dado r , si el conteo de círculos superpuestos de radio r en cualquier punto es mayor o igual a K. Se puede realizar mediante la siguiente técnica:
- Iterar a través de todos los posibles pares desordenados de los círculos dados y verificar si se cruzan entre sí. Supongamos que se cruzan entre sí. Entonces la situación se puede explicar con la siguiente imagen:
- La tarea es calcular el valor de P1 y P2 , lo que se puede hacer mediante el siguiente procedimiento:
dist = √( (x 1 – x 2 ) 2 + (y 1 – y 2 ) 2 ) [Usando la fórmula de la distancia]
h = √((mid) 2 – (dist/2) 2 ) [Usando el teorema de Pitágoras]Usando los valores de dist y h, P1 y P2 se pueden calcular mediante las siguientes fórmulas:
=> P1 = ( ((x1 + x2) + h * ( y1 – y2 )) / 2, ((y1 + y2) + h * ( x2 – x1 )) / 2) y de manera similar
=> P2 = ( ((x1 + x2) – h * ( y1 – y2 )) / 2, ((y1+ y2) – h * ( x2 – x1 )) / 2)
Por lo tanto, para todos los posibles pares de círculos que se intersecan, calcule el valor de P1 y P2 y calcule el número de círculos tal que P1 esté en esos círculos en una variable cnt1 y de manera similar calcule el número de círculos tal que P2 esté en ese círculo en un variable cnt2 . Si alguno de los valores de cnt1 y cnt2 es mayor que K , significa que para el r = mid dado , existe un punto en el plano tal que al menos K círculos se superponen sobre él.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
struct coord {
long double x, y;
};
// Function to find the square of the
// distance between two given points
long double distance(coord a, coord b)
{
// Distance Formulae
return (a.x - b.x) * (a.x - b.x)
+ (a.y - b.y) * (a.y - b.y);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
bool check(vector<coord> points, int k,
long double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for (int i = 0; i < points.size(); i++) {
for (int j = i + 1; j < points.size(); j++) {
// Stores the coordinates
// of 1st circle
coord C1 = points[i];
// Stores the coordinates
// of 2nd circle
coord C2 = points[j];
// Calculating dist and h
// as discussed in approach
long double dist = distance(C1, C2);
long double h
= sqrt((4 * mid - dist)
/ dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
coord P1, P2;
// By help of formulaes given above
P1.x = ((C1.x + C2.x)
+ h * (C1.y - C2.y))
/ 2;
P1.y = ((C1.y + C2.y)
+ h * (C2.x - C1.x))
/ 2;
P2.x = ((C1.x + C2.x)
- h * (C1.y - C2.y))
/ 2;
P2.y = ((C1.y + C2.y)
+ h * (C2.x - C1.x))
/ 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0, cnt2 = 0;
// Loop to traverse over all the circles
for (int k = 0; k < points.size(); k++) {
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid
<= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid
<= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k) {
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
int binSearchOnRad(vector<coord>& points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = 1e6;
// Loop to perform binary search
while (start <= end) {
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid)) {
end = mid - 1;
}
// If the required point
// does not exist
else {
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
int main()
{
vector<coord> points = { { 8, 5 },
{ 0, 4 },
{ 3, 6 } };
int K = 3;
cout << binSearchOnRad(points, K);
return 0;
}
Java
// Java implementation for the above approach
import java.io.*;
class GFG{
// Function to find the square of the
// distance between two given points
static double distance(double[] a, double[] b)
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0]) +
(a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
static boolean check(double[][] points, int k,
double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for(int i = 0; i < points.length; i++)
{
for(int j = i + 1; j < points.length; j++)
{
// Stores the coordinates
// of 1st circle
double[] C1 = points[i];
// Stores the coordinates
// of 2nd circle
double[] C2 = points[j];
// Calculating dist and h
// as discussed in approach
double dist = distance(C1, C2);
double h = Math.sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
double[] P1 = new double[2];
double[] P2 = new double[2];
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0]) +
h * (C1[1] - C2[1])) / 2;
P1[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
P2[0] = ((C1[0] + C2[0]) -
h * (C1[1] - C2[1])) / 2;
P2[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0;
int cnt2 = 0;
// Loop to traverse over all the circles
for(k = 0; k < points.length; k++)
{
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k)
{
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
static int binSearchOnRad(double[][] points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = (int)1e6;
// Loop to perform binary search
while (start <= end)
{
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid))
{
end = mid - 1;
}
// If the required point
// does not exist
else
{
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
public static void main(String[] args)
{
double[][] points = { { 8, 5 }, { 0, 4 }, { 3, 6 } };
int K = 3;
System.out.println(binSearchOnRad(points, K));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation of the above approach # Function to find the square of the # distance between two given points def distance(a, b): # Distance Formulae return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]) # Function to check if there exist a # point having K overlapping circles with # the radius of each circle as mid def check(points, k, mid): # Squaring the value of mid # for simplicity of calculation mid *= mid for i in range(len(points)): for j in range(i + 1, len(points)): # Stores the coordinates # of 1st circle C1 = points[i] # Stores the coordinates # of 2nd circle C2 = points[j] # Calculating dist and h # as discussed in approach dist = distance(C1, C2) h = ((4 * mid - dist) / dist) ** (1 / 2) # If Circles do not intersect if (dist > 4 * mid): continue # Stores two intersection points P1 = [0] * 2 P2 = [0] * 2 # By help of formulaes given above P1[0] = ((C1[0] + C2[0]) + h * (C1[1] - C2[1])) // 2 P1[1] = ((C1[1] + C2[1]) + h * (C2[0] - C1[0])) // 2 P2[0] = ((C1[0] + C2[0]) - h * (C1[1] - C2[1])) // 2 P2[1] = ((C1[1] + C2[1]) + h * (C2[0] - C1[0])) // 2 # Stores count of overlapping # circles over P1 and P2 cnt1 = 0 cnt2 = 0 # Loop to traverse over all the circles for k in range(len(points)): # If P1 lies inside Kth circle if (distance(P1, points[k]) - mid <= 0.000001): cnt1 += 1 # If P2 lies inside Kth circle if (distance(P2, points[k]) - mid <= 0.000001): cnt2 += 1 # If count of overlapping circles # is more than K if (cnt1 >= k or cnt2 >= k): return True # If no valid point is found return False # Function to perform the binary # search over the radius of the # circles in the range [0, ∞] def binSearchOnRad(points, k): # Stores the start and end of # range of the binary search start = 0 end = 1000000 # Loop to perform binary search while (start <= end): # Stores the mid if the # current range mid = start + (end - start) // 2 # If there exist a point having # k overlapping circles with the # radius of circles as mid if (check(points, k, mid)): end = mid - 1 # If the required point # does not exist else: start = mid + 1 # Return Answer return start # Driver Code points = [[8, 5], [0, 4], [3, 6]] K = 3 print(binSearchOnRad(points, K)) # This code is contributed by Saurabh Jaiswal
C#
// C# implementation for the above approach
using System;
class GFG {
// Function to find the square of the
// distance between two given points
static double distance(double[] a, double[] b)
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0])
+ (a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
static bool check(double[, ] points, int k, double mid)
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for (int i = 0; i < points.GetLength(0); i++) {
for (int j = i + 1; j < points.GetLength(0);
j++) {
// Stores the coordinates
// of 1st circle
double[] C1
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
C1[x] = points[i, x];
// Stores the coordinates
// of 2nd circle
double[] C2
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
C2[x] = points[j, x];
// Calculating dist and h
// as discussed in approach
double dist = distance(C1, C2);
double h
= Math.Sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
double[] P1 = new double[2];
double[] P2 = new double[2];
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0])
+ h * (C1[1] - C2[1]))
/ 2;
P1[1] = ((C1[1] + C2[1])
+ h * (C2[0] - C1[0]))
/ 2;
P2[0] = ((C1[0] + C2[0])
- h * (C1[1] - C2[1]))
/ 2;
P2[1] = ((C1[1] + C2[1])
+ h * (C2[0] - C1[0]))
/ 2;
// Stores count of overlapping
// circles over P1 and P2
int cnt1 = 0;
int cnt2 = 0;
// Loop to traverse over all the circles
for (k = 0; k < points.GetLength(0); k++) {
double[] P
= new double[points.GetLength(1)];
for (int x = 0; x < points.GetLength(1);
x++)
P[x] = points[k, x];
// If P1 lies inside Kth circle
if (distance(P1, P) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, P) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k) {
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
static int binSearchOnRad(double[, ] points, int k)
{
// Stores the start and end of
// range of the binary search
int start = 0, end = (int)1e6;
// Loop to perform binary search
while (start <= end) {
// Stores the mid if the
// current range
int mid = start + (end - start) / 2;
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid)) {
end = mid - 1;
}
// If the required point
// does not exist
else {
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
public static void Main(string[] args)
{
double[, ] points
= { { 8, 5 }, { 0, 4 }, { 3, 6 } };
int K = 3;
Console.WriteLine(binSearchOnRad(points, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript implementation of the above approach
// Function to find the square of the
// distance between two given points
const distance = (a, b) =>
{
// Distance Formulae
return (a[0] - b[0]) * (a[0] - b[0]) +
(a[1] - b[1]) * (a[1] - b[1]);
}
// Function to check if there exist a
// point having K overlapping circles with
// the radius of each circle as mid
const check = (points, k, mid) =>
{
// Squaring the value of mid
// for simplicity of calculation
mid *= mid;
for(let i = 0; i < points.length; i++)
{
for(let j = i + 1; j < points.length; j++)
{
// Stores the coordinates
// of 1st circle
let C1 = points[i];
// Stores the coordinates
// of 2nd circle
let C2 = points[j];
// Calculating dist and h
// as discussed in approach
let dist = distance(C1, C2);
let h = Math.sqrt((4 * mid - dist) / dist);
// If Circles do not intersect
if (dist > 4 * mid)
continue;
// Stores two intersection points
let P1 = new Array(2).fill(0),
P2 = new Array(2).fill(0);
// By help of formulaes given above
P1[0] = ((C1[0] + C2[0]) +
h * (C1[1] - C2[1])) / 2;
P1[1] = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
P2.x = ((C1[0] + C2[0]) -
h * (C1[1] - C2[1])) / 2;
P2.y = ((C1[1] + C2[1]) +
h * (C2[0] - C1[0])) / 2;
// Stores count of overlapping
// circles over P1 and P2
let cnt1 = 0, cnt2 = 0;
// Loop to traverse over all the circles
for(let k = 0; k < points.length; k++)
{
// If P1 lies inside Kth circle
if (distance(P1, points[k]) - mid <= 0.000001)
cnt1++;
// If P2 lies inside Kth circle
if (distance(P2, points[k]) - mid <= 0.000001)
cnt2++;
}
// If count of overlapping circles
// is more than K
if (cnt1 >= k || cnt2 >= k)
{
return true;
}
}
}
// If no valid point is found
return false;
}
// Function to perform the binary
// search over the radius of the
// circles in the range [0, ∞]
const binSearchOnRad = (points, k) =>
{
// Stores the start and end of
// range of the binary search
let start = 0, end = 1000000;
// Loop to perform binary search
while (start <= end)
{
// Stores the mid if the
// current range
let mid = start + parseInt((end - start) / 2);
// If there exist a point having
// k overlapping circles with the
// radius of circles as mid
if (check(points, k, mid))
{
end = mid - 1;
}
// If the required point
// does not exist
else
{
start = mid + 1;
}
}
// Return Answer
return start;
}
// Driver Code
let points = [ [ 8, 5 ], [ 0, 4 ], [ 3, 6 ] ];
let K = 3;
document.write(binSearchOnRad(points, K));
// This code is contributed by rakeshsahni
</script>
Producción
5
Complejidad de Tiempo: O(N 3 * log N)
Espacio Auxiliar: O(1)