Given N points on a 2D infinite plane, where each point represents the center of a circle initially having a radius of 0 which expands at a constant rate of 1 unit per second, the task is to find the minimum time at which at least K circles overlap at a point.
Example:
Input: points[] = {{8, 5}, {0, 4}, {3, 6}}, K = 3
Output: 5
Explanation: Consider infinite grid as shown in the image below. the image shows the state of the circles after 5 seconds. Each of the three circles overlap and all the points in the yellow highlighted region has at least 3 overlapping circles. Therefore, after 5 seconds, there exists a point on the plane (i.e, (5, 4)) such that at least 3 circles overlap it and it is the minimum possible time.
Input: points[] = {{0, 0}, {1, 1}, {2, 2}}, K = 2
Output: 1
Approach: The given problem
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 pointslong 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 midbool 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 Codeint 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 approachimport java.io.*;class GFG{// Function to find the square of the// distance between two given pointsstatic 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 midstatic 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 Codepublic 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 pointsdef 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 middef 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 Codepoints = [[8, 5], [0, 4], [3, 6]]K = 3print(binSearchOnRad(points, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# implementation for the above approachusing 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 pointsconst 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 midconst 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 Codelet points = [ [ 8, 5 ], [ 0, 4 ], [ 3, 6 ] ];let K = 3;document.write(binSearchOnRad(points, K));// This code is contributed by rakeshsahni</script> |
can be solved with the help of the binary search using the following observations:
- At any given time t, the radius of all the circles must be t. Therefore, the problem can be converted into finding the smallest radius such that at least K circles overlap at a given point.
- The smallest required radius can be calculated by performing a binary search over it in the range [0, ∞].
Now, the required task is to check for a given radius r, if the count of overlapping circles of radius r at any point is more than or equal to K. It can be done using the following technique:
- Iterate through all possible unordered pairs of the given circles and check if they intersect with each other. Suppose they intersect with each other. Then the situation can be explained by the following image:
- The task is to calculate the value of P1 and P2 which can be done by the following procedure:
dist = √( (x1 – x2)2 + (y1 – y2)2) [Using the distance formula]
h = √((mid)2 – (dist/2)2) [Using the Pythagorean theorem]Using the values of dist and h, P1 and P2 can be calculated by the following formulae:
=> P1 = ( ((x1 + x2) + h * ( y1 – y2 )) / 2, ((y1 + y2) + h * ( x2 – x1 )) / 2) and similarly
=> P2 = ( ((x1 + x2) – h * ( y1 – y2 )) / 2, ((y1+ y2) – h * ( x2 – x1 )) / 2)
Therefore, for all possible pairs of intersecting circles, calculate the value of P1 and P2 and calculate the count of circles such that P1 lies in that circles in a variable cnt1 and similarly calculate the count of circles such that P2 lies in that circle in a variable cnt2. If any of the values of cnt1 and cnt2 is greater than K, it means for the given r = mid, there exists a point in the plane such that at least K circles overlap over it.
Below is the implementation of the above approach:
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 pointslong 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 midbool 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 Codeint 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 approachimport java.io.*;class GFG{// Function to find the square of the// distance between two given pointsstatic 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 midstatic 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 Codepublic 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 pointsdef 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 middef 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 Codepoints = [[8, 5], [0, 4], [3, 6]]K = 3print(binSearchOnRad(points, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# implementation for the above approachusing 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 pointsconst 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 midconst 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 Codelet points = [ [ 8, 5 ], [ 0, 4 ], [ 3, 6 ] ];let K = 3;document.write(binSearchOnRad(points, K));// This code is contributed by rakeshsahni</script> |
Output
5
Time Complexity: O(N3 * log N)
Auxiliary Space: O(1)
