Given an array arr[][] of size N, consisting of pairs of coordinates such that arr[i][0] and arr[i][1] represents the X and Y coordinates in a 2D plane. Given another array V[] that denotes the maximum velocity of each point in any direction, the task is to find the minimum time such that all the given points meet at any arbitrary points in the 2D plane.
Examples:
Input: N = 4, arr[][] = {{1, 2}, {-3, 34}, {-1, -2}, {2, -2}}, V[] = {3, 2, 4, 5}
Output: 1.1157499537009508Input: N = 2, arr[][] = {{1. 2}, {-1, -2}}, V[] = {2, 3}
Output: 0.8944271909999159
Approach: The given problem can be solved based on the following observations:
- The given N points in the coordinates axis can move in any direction and if these points are allowed to move for T time then they can reach any point within the circle (by reducing V[i] accordingly) having a radius equal to V[i] * T and centre equal to initial position of the point, where V[i] represents the speed of the ith point.
- Therefore, to minimize the common area of these N circles radius needs to be minimized and if there exists a common meeting point in time T then there must exist a meeting point for T’ > T as there will be a more common area for T’.
- Hence, the idea is to check for the existence of a common meeting point i.e., check for the existence of a common area of N circles.
- Below is the illustration for all possible combinations of 3 circles and each has a non-zero area of intersection then all the 3 circles have a common area of intersection as:
- In Fig 1, 2, 3, 4, 5 the sum of the radius of two of the three circles is less than the distance between them which means there is no common area among the three circles.
- In Fig 6, 7, 8, 9 one or two circle(s) lie within another circle.
- In Fig 10, 11, 12, 13 find the intersection between two circles and check whether those intersection points lie within the other circle or not.
From the above observations, the idea is to use Binary Search for finding the minimum time with a unique point of intersection for all the given N points. Follow the steps below to solve the given problem:
- Declare a function, say intersection(X1, Y1, R1, X2, Y2, R2, X3, Y3, R3) that takes the coordinates and radius of the circles as a parameter and perform the following steps:
- If the sum of radiuses of any two circles is less than the sum of distances between their centers, then return false as there doesn’t exist any such common area between them.
- Now, check if any two circles have a common area or not. If found to be true, then return true. Otherwise, return false.
- Declare a function, say isGood(mid, N, X, Y, V) that takes the current possible time, coordinates of the N points, and velocity of each point as a parameter and perform the following steps:
- If the value of N is at least 3, then check for all possible combinations of three circles to get the common area by calling the function intersection(X1, Y1, R1, X2, Y2, R2, X3, Y3, R3). If there exists any such combination that doesn’t have any common area then return false. Otherwise, return true.
- If the value of N is 2, then check if the two circles have a common area or not. If found to be true, then return true. Otherwise, return false.
- Initialize two variables, say tl as 0.0 and tu as 100000.0 as the minimum and maximum time required to get the unique point of intersection respectively.
- Now, iterate over the range [0, 1000] to get the better precision of the resultant time and perform a binary search by following the below steps:
- Find the middle value, say mid as (tl + tu)/2.0.
- Now check if the above time mid has at least one common area of intersections or not by calling the function isGood(mid, N, X, Y, V). If found to be true, then update tu as mid. Otherwise, update tl as t.
- After completing the above steps, print the value of tu as the resultant minimum time for all the given N points intersecting at one point.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to check for common area// between three circlesbool intersection(int X1, int Y1, double R1, int X2, int Y2, double R2, int X3, int Y3, double R3){ // Find the distance between the // centers of circle 1 & circle 2 double d12 = sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)); // Find the distance between the // centers of circle 1 & circle 3 double d13 = sqrt((X1 - X3) * (X1 - X3) + (Y1 - Y3) * (Y1 - Y3)); // Find the distance between the // centers of circle 2 & circle 3 double d23 = sqrt((X2 - X3) * (X2 - X3) + (Y2 - Y3) * (Y2 - Y3)); // If sum of radius is less than // the distance between their // centers then false if ((R1 + R2 < d12) || (R1 + R3 < d13) || (R2 + R3 < d23)) { return false; } else { // If circle 1 lies within // circle 2 or if circle // 2 lies within circle 1 if (abs(R1 - R2) >= d12) { // If circle 1 lies // within circle 2 if (R1 < R2) { // Check whether R1 // (common area between // R1 and R2) and // R3 intersect return R1 + R3 >= d13; } else { // Check whether R2 //(common area between // R1 and R2) and // R3 intersect return R2 + R3 >= d23; } } // If circle 1 lies within // circle 3 or if circle // 3 lies within circle 1 else if (abs(R1 - R3) >= d13) { // If circle 1 lies // within circle 3 if (R1 < R3) { // Check whether R1 // (common area between // R1 and R3) and // R2 intersect return R1 + R2 >= d12; } else { // Check whether R3 //(common area between // R1 and R3) and // R2 intersect return R2 + R3 >= d23; } } // If circle 2 lies within // circle 3 or if circle // 3 lies within circle 2 else if (abs(R2 - R3) >= d23) { // If circle 2 // lies within circle 3 if (R2 < R3) { // Check whether R2 // (common area between // R2 and R3) and // R1 intersect return R1 + R2 >= d12; } else { // Check whether R3 // (common area between // R2 and R3) and // R1 intersect return R1 + R3 >= d13; } } else { double x121, y121, x122, y122, x131, y131, x132, y132, x231, y231, x232, y232, a, b; // Find the point of // intersection for // circle 1 & circle 2 a = (R1 * R1 - R2 * R2) / (2 * d12 * d12); b = sqrt(2 * (R1 * R1 + R2 * R2) / (d12 * d12) - (R1 * R1 - R2 * R2) * (R1 * R1 - R2 * R2) / (pow(d12, 4)) - 1) / 2; // First point of // intersection (x121, y121) x121 = (X1 + X2) / 2.0 + a * (X2 - X1) + b * (Y2 - Y1); y121 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) + b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= sqrt( (x121 - X3) * (x121 - X3) + (y121 - Y3) * (y121 - Y3))) { return true; } // Second point of // intersection(x122, y122) x122 = (X1 + X2) / 2.0 + a * (X2 - X1) - b * (Y2 - Y1); y122 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) - b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= sqrt( (x122 - X3) * (x122 - X3) + (y122 - Y3) * (y122 - Y3))) { return true; } // Find the point of // intersection for // circle 1 & circle 3 a = (R1 * R1 - R3 * R3) / (2 * d13 * d13); b = sqrt(2 * (R1 * R1 + R3 * R3) / (d13 * d13) - (R1 * R1 - R3 * R3) * (R1 * R1 - R3 * R3) / (pow(d13, 4)) - 1) / 2; // First point of // intersection(x131, y131) x131 = (X1 + X3) / 2.0 + a * (X3 - X1) + b * (Y3 - Y1); y131 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) + b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= sqrt( (x131 - X2) * (x131 - X2) + (y131 - Y2) * (y131 - Y2))) { return true; } // Second point of // intersection(x132, y132) x132 = (X1 + X3) / 2.0 + a * (X3 - X1) - b * (Y3 - Y1); y132 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) - b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= sqrt( (x132 - X2) * (x132 - X2) + (y132 - Y2) * (y132 - Y2))) { return true; } // Find the point of // intersection for // circle 2 & circle 3 a = (R2 * R2 - R3 * R3) / (2 * d23 * d23); b = sqrt(2 * (R2 * R2 + R3 * R3) / (d23 * d23) - (R2 * R2 - R3 * R3) * (R2 * R2 - R3 * R3) / (pow(d23, 4)) - 1) / 2; // First point of // intersection(x231, y231) x231 = (X2 + X3) / 2.0 + a * (X3 - X2) + b * (Y3 - Y2); y231 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) + b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not if (R1 >= sqrt( (x231 - X1) * (x231 - X1) + (y231 - Y1) * (y231 - Y1))) { return true; } // Second point of // intersection(x232, y232) x232 = (X2 + X3) / 2.0 + a * (X3 - X2) - b * (Y3 - Y2); y232 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) - b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not return R1 >= sqrt( (x232 - X1) * (x232 - X1) + (y232 - Y1) * (y232 - Y1)); } }}// Function to check if there is// a common area between N// circlesbool isGood(double t, int N, int X[], int Y[], int V[]){ if (N >= 3) { // Check for a common area // for all combination // of 3 circles for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { // t * V give the // radius of the circle if (intersection( X[i], Y[i], t * V[i], X[j], Y[j], t * V[j], X[k], Y[k], t * V[k]) == false) return false; } } } return true; } // For N = 2 else { //(x2 - x1) ^ 2 + (y2 - y1) ^ 2 <= //(r1 + r2) ^ 2 for 2 circles // to intersect return sqrt((X[0] - X[1]) * (X[0] - X[1]) + (Y[0] - Y[1]) * (Y[0] - Y[1])) <= t * (V[0] + V[1]); }}// Function to find minimum timevoid binarySearch(int N, int X[], int Y[], int V[]){ // Time depends on the area // of the 2D plane // Area =(Max(X) - Min(X))* // (Max(Y) - Min(Y)) double tl = 0.0, tu = 100000.0, t; // Number of iteration // depends on the precision for (int i = 0; i < 1000; i++) { t = (tl + tu) / 2.0; // If there is a common area // between N circles // for time t if (isGood(t, N, X, Y, V)) { tu = t; } // If there is no common area // between N circles // for time t else { tl = t; } } // Print the minimum time cout << fixed << setprecision(16) << tu << endl;}// Driver Codeint main(){ int N = 4; int X[] = { 1, -3, -1, 2 }; int Y[] = { 2, 4, -2, -2 }; int V[] = { 3, 2, 4, 5 }; // Function Call binarySearch(N, X, Y, V);}// This code is contributed by ipg2016107. |
Java
// Java program for the above approachclass GFG { // Function to check for common area // between three circles public static boolean intersection(int X1, int Y1, double R1, int X2, int Y2, double R2, int X3, int Y3, double R3) { // Find the distance between the // centers of circle 1 & circle 2 double d12 = Math.sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)); // Find the distance between the // centers of circle 1 & circle 3 double d13 = Math.sqrt((X1 - X3) * (X1 - X3) + (Y1 - Y3) * (Y1 - Y3)); // Find the distance between the // centers of circle 2 & circle 3 double d23 = Math.sqrt((X2 - X3) * (X2 - X3) + (Y2 - Y3) * (Y2 - Y3)); // If sum of radius is less than // the distance between their // centers then false if ((R1 + R2 < d12) || (R1 + R3 < d13) || (R2 + R3 < d23)) { return false; } else { // If circle 1 lies within // circle 2 or if circle // 2 lies within circle 1 if (Math.abs(R1 - R2) >= d12) { // If circle 1 lies // within circle 2 if (R1 < R2) { // Check whether R1 // (common area between // R1 and R2) and // R3 intersect return R1 + R3 >= d13; } else { // Check whether R2 //(common area between // R1 and R2) and // R3 intersect return R2 + R3 >= d23; } } // If circle 1 lies within // circle 3 or if circle // 3 lies within circle 1 else if (Math.abs(R1 - R3) >= d13) { // If circle 1 lies // within circle 3 if (R1 < R3) { // Check whether R1 // (common area between // R1 and R3) and // R2 intersect return R1 + R2 >= d12; } else { // Check whether R3 //(common area between // R1 and R3) and // R2 intersect return R2 + R3 >= d23; } } // If circle 2 lies within // circle 3 or if circle // 3 lies within circle 2 else if (Math.abs(R2 - R3) >= d23) { // If circle 2 // lies within circle 3 if (R2 < R3) { // Check whether R2 // (common area between // R2 and R3) and // R1 intersect return R1 + R2 >= d12; } else { // Check whether R3 // (common area between // R2 and R3) and // R1 intersect return R1 + R3 >= d13; } } else { double x121, y121, x122, y122, x131, y131, x132, y132, x231, y231, x232, y232, a, b; // Find the point of // intersection for // circle 1 & circle 2 a = (R1 * R1 - R2 * R2) / (2 * d12 * d12); b = Math.sqrt(2 * (R1 * R1 + R2 * R2) / (d12 * d12) - (R1 * R1 - R2 * R2) * (R1 * R1 - R2 * R2) / (Math.pow(d12, 4)) - 1) / 2; // First point of // intersection (x121, y121) x121 = (X1 + X2) / 2.0 + a * (X2 - X1) + b * (Y2 - Y1); y121 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) + b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.sqrt( (x121 - X3) * (x121 - X3) + (y121 - Y3) * (y121 - Y3))) { return true; } // Second point of // intersection(x122, y122) x122 = (X1 + X2) / 2.0 + a * (X2 - X1) - b * (Y2 - Y1); y122 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) - b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.sqrt( (x122 - X3) * (x122 - X3) + (y122 - Y3) * (y122 - Y3))) { return true; } // Find the point of // intersection for // circle 1 & circle 3 a = (R1 * R1 - R3 * R3) / (2 * d13 * d13); b = Math.sqrt(2 * (R1 * R1 + R3 * R3) / (d13 * d13) - (R1 * R1 - R3 * R3) * (R1 * R1 - R3 * R3) / (Math.pow(d13, 4)) - 1) / 2; // First point of // intersection(x131, y131) x131 = (X1 + X3) / 2.0 + a * (X3 - X1) + b * (Y3 - Y1); y131 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) + b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.sqrt( (x131 - X2) * (x131 - X2) + (y131 - Y2) * (y131 - Y2))) { return true; } // Second point of // intersection(x132, y132) x132 = (X1 + X3) / 2.0 + a * (X3 - X1) - b * (Y3 - Y1); y132 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) - b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.sqrt( (x132 - X2) * (x132 - X2) + (y132 - Y2) * (y132 - Y2))) { return true; } // Find the point of // intersection for // circle 2 & circle 3 a = (R2 * R2 - R3 * R3) / (2 * d23 * d23); b = Math.sqrt(2 * (R2 * R2 + R3 * R3) / (d23 * d23) - (R2 * R2 - R3 * R3) * (R2 * R2 - R3 * R3) / (Math.pow(d23, 4)) - 1) / 2; // First point of // intersection(x231, y231) x231 = (X2 + X3) / 2.0 + a * (X3 - X2) + b * (Y3 - Y2); y231 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) + b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not if (R1 >= Math.sqrt( (x231 - X1) * (x231 - X1) + (y231 - Y1) * (y231 - Y1))) { return true; } // Second point of // intersection(x232, y232) x232 = (X2 + X3) / 2.0 + a * (X3 - X2) - b * (Y3 - Y2); y232 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) - b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not return R1 >= Math.sqrt( (x232 - X1) * (x232 - X1) + (y232 - Y1) * (y232 - Y1)); } } } // Function to check if there is // a common area between N // circles public static boolean isGood(double t, int N, int[] X, int[] Y, int[] V) { if (N >= 3) { // Check for a common area // for all combination // of 3 circles for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { for (int k = j + 1; k < N; k++) { // t * V give the // radius of the circle if (!intersection( X[i], Y[i], t * V[i], X[j], Y[j], t * V[j], X[k], Y[k], t * V[k])) return false; } } } return true; } // For N = 2 else { //(x2 - x1) ^ 2 + (y2 - y1) ^ 2 <= //(r1 + r2) ^ 2 for 2 circles // to intersect return Math.sqrt((X[0] - X[1]) * (X[0] - X[1]) + (Y[0] - Y[1]) * (Y[0] - Y[1])) <= t * (V[0] + V[1]); } } // Function to find minimum time public static void binarySearch(int N, int[] X, int[] Y, int[] V) { // Time depends on the area // of the 2D plane // Area =(Max(X) - Min(X))* // (Max(Y) - Min(Y)) double tl = 0.0, tu = 100000.0, t; // Number of iteration // depends on the precision for (int i = 0; i < 1000; i++) { t = (tl + tu) / 2.0; // If there is a common area // between N circles // for time t if (isGood(t, N, X, Y, V)) { tu = t; } // If there is no common area // between N circles // for time t else { tl = t; } } // Print the minimum time System.out.println(tu); } // Driver Code public static void main(String[] args) { int N = 4; int[] X = { 1, -3, -1, 2 }; int[] Y = { 2, 4, -2, -2 }; int[] V = { 3, 2, 4, 5 }; // Function Call binarySearch(N, X, Y, V); }} |
Python3
# Python program for the above approachimport math # Function to check for common area # between three circlesdef intersection(X1, Y1, R1, X2, Y2, R2, X3, Y3, R3): # Find the distance between the # centers of circle 1 & circle 2 d12 = math.sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)) # Find the distance between the # centers of circle 1 & circle 3 d13 = math.sqrt((X1 - X3) * (X1 - X3) + (Y1 - Y3) * (Y1 - Y3)) # Find the distance between the # centers of circle 2 & circle 3 d23 = math.sqrt((X2 - X3) * (X2 - X3) + (Y2 - Y3) * (Y2 - Y3)) # If sum of radius is less than # the distance between their # centers then false if R1 + R2 < d12 or R1 + R3 < d13 or R2 + R3 < d23: return False else: # If circle 1 lies within # circle 2 or if circle # 2 lies within circle 1 if abs(R1 - R2) >= d12: # If circle 1 lies # within circle 2 if R1 < R2: # Check whether R1 # (common area between # R1 and R2) and # R3 intersect return R1 + R3 >= d13 else: # Check whether R2 # (common area between # R1 and R2) and # R3 intersect return R2 + R3 >= d23 # If circle 1 lies within # circle 3 or if circle # 3 lies within circle 1 elif abs(R1 - R3) >= d13: # If circle 1 lies # within circle 3 if (R1 < R3): # Check whether R1 # (common area between # R1 and R3) and # R2 intersect return R1 + R2 >= d12 else: # Check whether R3 # (common area between # R1 and R3) and # R2 intersect return R2 + R3 >= d23 # If circle 2 lies within # circle 3 or if circle # 3 lies within circle 2 elif(abs(R2 - R3) >= d23): # If circle 2 # lies within circle 3 if (R2 < R3): # Check whether R2 # (common area between # R2 and R3) and # R1 intersect return R1 + R2 >= d12 else: # Check whether R3 # (common area between # R2 and R3) and # R1 intersect return R1 + R3 >= d13 else: # Find the point of # intersection for # circle 1 & circle 2 a = (R1 * R1 - R2 * R2) / (2 * d12 * d12) b = math.sqrt(2 * (R1 * R1 + R2 * R2) / (d12 * d12) - (R1 * R1 - R2 * R2) * (R1 * R1 - R2 * R2)/ (pow(d12, 4)) - 1) # First point of # intersection (x121, y121) x121 = (X1 + X2) / 2.0 + a * (X2 - X1) + b * (Y2 - Y1) y121 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1)+ b * (X1 - X2) # Check whether the point # of intersection lies # within circle 3 or not if (R3 >= math.sqrt((x121 - X3) * (x121 - X3) + (y121 - Y3) * (y121 - Y3))): return True # Second point of # intersection(x122, y122) x122 = (X1 + X2) / 2.0 + a * (X2 - X1) - b * (Y2 - Y1) y122 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) - b * (X1 - X2) # Check whether the point # of intersection lies # within circle 3 or not if (R3 >= math.sqrt((x122 - X3) * (x122 - X3)+ (y122 - Y3) * (y122 - Y3))): return True # Find the point of # intersection for # circle 1 & circle 3 a = (R1 * R1 - R3 * R3) / (2 * d13 * d13) b = math.sqrt(2 * (R1 * R1 + R3 * R3)/ (d13 * d13)- (R1 * R1 - R3 * R3)* (R1 * R1 - R3 * R3)/ (math.pow(d13, 4))- 1)/ 2 # First point of # intersection(x131, y131) x131 = (X1 + X3) / 2.0 + a * (X3 - X1) + b * (Y3 - Y1) y131 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) + b * (X1 - X3) # Check whether the point # of intersection lies # within circle 2 or not if (R2 >= math.sqrt( (x131 - X2) * (x131 - X2) + (y131 - Y2) * (y131 - Y2))): return True # Second point of # intersection(x132, y132) x132 = (X1 + X3) / 2.0 + a * (X3 - X1) - b * (Y3 - Y1) y132 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) - b * (X1 - X3) # Check whether the point # of intersection lies # within circle 2 or not if (R2 >= math.sqrt( (x132 - X2) * (x132 - X2) + (y132 - Y2) * (y132 - Y2))): return True # Find the point of # intersection for # circle 2 & circle 3 a = (R2 * R2 - R3 * R3) / (2 * d23 * d23) # b = math.sqrt(2 * (R2 * R2 + R3 * R3) / (d23 * d23) - (R2 * R2 - R3 * R3) * (R2 * R2 - R3 * R3) / (pow(d23, 4)) - 1)/2 # First point of # intersection(x231, y231) x231 = (X2 + X3) / 2.0 + a * (X3 - X2) + b * (Y3 - Y2) y231 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) + b * (X2 - X3) # Check whether the point # of intersection lies # within circle 1 or not if (R1 >= math.sqrt( (x231 - X1) * (x231 - X1) + (y231 - Y1) * (y231 - Y1))): return True # Second point of # intersection(x232, y232) x232 = (X2 + X3) / 2.0 + a * (X3 - X2) - b * (Y3 - Y2) y232 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) - b * (X2 - X3) # Check whether the point # of intersection lies # within circle 1 or not return R1 >= math.sqrt( (x232 - X1) * (x232 - X1) + (y232 - Y1) * (y232 - Y1)) # Function to check if there is# a common area between N# circlesdef isGood(t, N, X, Y, V): if N >= 3: # Check for a common area # for all combination # of 3 circles for i in range(N): for j in range(i+1, N): for k in range(j+1, N): # t * V give the # radius of the circle if (intersection(X[i], Y[i], t * V[i], X[j],Y[j], t * V[j], X[k], Y[k],t * V[k])): pass else: return False return True # For N = 2 else: # (x2 - x1) ^ 2 + (y2 - y1) ^ 2 <= # (r1 + r2) ^ 2 for 2 circles # to intersect return math.sqrt((X[0] - X[1]) * (X[0] - X[1]) + (Y[0] - Y[1]) * (Y[0] - Y[1])) <= t * (V[0] + V[1])# Function to find minimum timedef binarySearch(N, X, Y, V): # Time depends on the area # of the 2D plane # Area =(Max(X) - Min(X))* # (Max(Y) - Min(Y)) tl = 0.0 tu = 100000.0 # Number of iteration # depends on the precision for i in range(1000): t = (tl + tu) / 2.0 # If there is a common area # between N circles # for time t if (isGood(t, N, X, Y, V)): tu = t # If there is no common area # between N circles # for time t else: tl = t # Print the minimum time print(tu)# Driver CodeN = 4X = [1, -3, -1, 2]Y = [2, 4, -2, -2]V = [3, 2, 4, 5]# Function CallbinarySearch(N, X, Y, V)# This code is contributed by Gautam goel(gautamgoel962). |
C#
// C# program for the above approachusing System;class GFG{// Function to check for common area// between three circlespublic static bool intersection(int X1, int Y1, double R1, int X2, int Y2, double R2, int X3, int Y3, double R3){ // Find the distance between the // centers of circle 1 & circle 2 double d12 = Math.Sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)); // Find the distance between the // centers of circle 1 & circle 3 double d13 = Math.Sqrt((X1 - X3) * (X1 - X3) + (Y1 - Y3) * (Y1 - Y3)); // Find the distance between the // centers of circle 2 & circle 3 double d23 = Math.Sqrt((X2 - X3) * (X2 - X3) + (Y2 - Y3) * (Y2 - Y3)); // If sum of radius is less than // the distance between their // centers then false if ((R1 + R2 < d12) || (R1 + R3 < d13) || (R2 + R3 < d23)) { return false; } else { // If circle 1 lies within // circle 2 or if circle // 2 lies within circle 1 if (Math.Abs(R1 - R2) >= d12) { // If circle 1 lies // within circle 2 if (R1 < R2) { // Check whether R1 // (common area between // R1 and R2) and // R3 intersect return R1 + R3 >= d13; } else { // Check whether R2 //(common area between // R1 and R2) and // R3 intersect return R2 + R3 >= d23; } } // If circle 1 lies within // circle 3 or if circle // 3 lies within circle 1 else if (Math.Abs(R1 - R3) >= d13) { // If circle 1 lies // within circle 3 if (R1 < R3) { // Check whether R1 // (common area between // R1 and R3) and // R2 intersect return R1 + R2 >= d12; } else { // Check whether R3 //(common area between // R1 and R3) and // R2 intersect return R2 + R3 >= d23; } } // If circle 2 lies within // circle 3 or if circle // 3 lies within circle 2 else if (Math.Abs(R2 - R3) >= d23) { // If circle 2 // lies within circle 3 if (R2 < R3) { // Check whether R2 // (common area between // R2 and R3) and // R1 intersect return R1 + R2 >= d12; } else { // Check whether R3 // (common area between // R2 and R3) and // R1 intersect return R1 + R3 >= d13; } } else { double x121, y121, x122, y122, x131, y131, x132, y132, x231, y231, x232, y232, a, b; // Find the point of // intersection for // circle 1 & circle 2 a = (R1 * R1 - R2 * R2) / (2 * d12 * d12); b = Math.Sqrt(2 * (R1 * R1 + R2 * R2) / (d12 * d12) - (R1 * R1 - R2 * R2) * (R1 * R1 - R2 * R2) / (Math.Pow(d12, 4)) - 1) / 2; // First point of // intersection (x121, y121) x121 = (X1 + X2) / 2.0 + a * (X2 - X1) + b * (Y2 - Y1); y121 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) + b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.Sqrt((x121 - X3) * (x121 - X3) + (y121 - Y3) * (y121 - Y3))) { return true; } // Second point of // intersection(x122, y122) x122 = (X1 + X2) / 2.0 + a * (X2 - X1) - b * (Y2 - Y1); y122 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) - b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.Sqrt((x122 - X3) * (x122 - X3) + (y122 - Y3) * (y122 - Y3))) { return true; } // Find the point of // intersection for // circle 1 & circle 3 a = (R1 * R1 - R3 * R3) / (2 * d13 * d13); b = Math.Sqrt(2 * (R1 * R1 + R3 * R3) / (d13 * d13) - (R1 * R1 - R3 * R3) * (R1 * R1 - R3 * R3) / (Math.Pow(d13, 4)) - 1) / 2; // First point of // intersection(x131, y131) x131 = (X1 + X3) / 2.0 + a * (X3 - X1) + b * (Y3 - Y1); y131 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) + b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.Sqrt((x131 - X2) * (x131 - X2) + (y131 - Y2) * (y131 - Y2))) { return true; } // Second point of // intersection(x132, y132) x132 = (X1 + X3) / 2.0 + a * (X3 - X1) - b * (Y3 - Y1); y132 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) - b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.Sqrt((x132 - X2) * (x132 - X2) + (y132 - Y2) * (y132 - Y2))) { return true; } // Find the point of // intersection for // circle 2 & circle 3 a = (R2 * R2 - R3 * R3) / (2 * d23 * d23); b = Math.Sqrt(2 * (R2 * R2 + R3 * R3) / (d23 * d23) - (R2 * R2 - R3 * R3) * (R2 * R2 - R3 * R3) / (Math.Pow(d23, 4)) - 1) / 2; // First point of // intersection(x231, y231) x231 = (X2 + X3) / 2.0 + a * (X3 - X2) + b * (Y3 - Y2); y231 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) + b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not if (R1 >= Math.Sqrt((x231 - X1) * (x231 - X1) + (y231 - Y1) * (y231 - Y1))) { return true; } // Second point of // intersection(x232, y232) x232 = (X2 + X3) / 2.0 + a * (X3 - X2) - b * (Y3 - Y2); y232 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) - b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not return R1 >= Math.Sqrt((x232 - X1) * (x232 - X1) + (y232 - Y1) * (y232 - Y1)); } }}// Function to check if there is// a common area between N// circlespublic static bool isGood(double t, int N, int[] X, int[] Y, int[] V){ if (N >= 3) { // Check for a common area // for all combination // of 3 circles for(int i = 0; i < N; i++) { for(int j = i + 1; j < N; j++) { for(int k = j + 1; k < N; k++) { // t * V give the // radius of the circle if (!intersection(X[i], Y[i], t * V[i], X[j], Y[j], t * V[j], X[k], Y[k], t * V[k])) return false; } } } return true; } // For N = 2 else { //(x2 - x1) ^ 2 + (y2 - y1) ^ 2 <= //(r1 + r2) ^ 2 for 2 circles // to intersect return Math.Sqrt((X[0] - X[1]) * (X[0] - X[1]) + (Y[0] - Y[1]) * (Y[0] - Y[1])) <= t * (V[0] + V[1]); }}// Function to find minimum timepublic static void binarySearch(int N, int[] X, int[] Y, int[] V){ // Time depends on the area // of the 2D plane // Area =(Max(X) - Min(X))* // (Max(Y) - Min(Y)) double tl = 0.0, tu = 100000.0, t; // Number of iteration // depends on the precision for(int i = 0; i < 1000; i++) { t = (tl + tu) / 2.0; // If there is a common area // between N circles // for time t if (isGood(t, N, X, Y, V)) { tu = t; } // If there is no common area // between N circles // for time t else { tl = t; } } // Print the minimum time Console.WriteLine(tu);}// Driver Codepublic static void Main(string[] args){ int N = 4; int[] X = { 1, -3, -1, 2 }; int[] Y = { 2, 4, -2, -2 }; int[] V = { 3, 2, 4, 5 }; // Function Call binarySearch(N, X, Y, V);}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program for the above approach// Function to check for common area// between three circlesfunction intersection(X1, Y1, R1, X2, Y2, R2, X3, Y3, R3) { // Find the distance between the // centers of circle 1 & circle 2 let d12 = Math.sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2)); // Find the distance between the // centers of circle 1 & circle 3 let d13 = Math.sqrt((X1 - X3) * (X1 - X3) + (Y1 - Y3) * (Y1 - Y3)); // Find the distance between the // centers of circle 2 & circle 3 let d23 = Math.sqrt((X2 - X3) * (X2 - X3) + (Y2 - Y3) * (Y2 - Y3)); // If sum of radius is less than // the distance between their // centers then false if ((R1 + R2 < d12) || (R1 + R3 < d13) || (R2 + R3 < d23)) { return false; } else { // If circle 1 lies within // circle 2 or if circle // 2 lies within circle 1 if (Math.abs(R1 - R2) >= d12) { // If circle 1 lies // within circle 2 if (R1 < R2) { // Check whether R1 // (common area between // R1 and R2) and // R3 intersect return R1 + R3 >= d13; } else { // Check whether R2 //(common area between // R1 and R2) and // R3 intersect return R2 + R3 >= d23; } } // If circle 1 lies within // circle 3 or if circle // 3 lies within circle 1 else if (Math.abs(R1 - R3) >= d13) { // If circle 1 lies // within circle 3 if (R1 < R3) { // Check whether R1 // (common area between // R1 and R3) and // R2 intersect return R1 + R2 >= d12; } else { // Check whether R3 //(common area between // R1 and R3) and // R2 intersect return R2 + R3 >= d23; } } // If circle 2 lies within // circle 3 or if circle // 3 lies within circle 2 else if (Math.abs(R2 - R3) >= d23) { // If circle 2 // lies within circle 3 if (R2 < R3) { // Check whether R2 // (common area between // R2 and R3) and // R1 intersect return R1 + R2 >= d12; } else { // Check whether R3 // (common area between // R2 and R3) and // R1 intersect return R1 + R3 >= d13; } } else { let x121, y121, x122, y122, x131, y131, x132, y132, x231, y231, x232, y232, a, b; // Find the point of // intersection for // circle 1 & circle 2 a = (R1 * R1 - R2 * R2) / (2 * d12 * d12); b = Math.sqrt(2 * (R1 * R1 + R2 * R2) / (d12 * d12) - (R1 * R1 - R2 * R2) * (R1 * R1 - R2 * R2) / (Math.pow(d12, 4)) - 1) / 2; // First point of // intersection (x121, y121) x121 = (X1 + X2) / 2.0 + a * (X2 - X1) + b * (Y2 - Y1); y121 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) + b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.sqrt( (x121 - X3) * (x121 - X3) + (y121 - Y3) * (y121 - Y3))) { return true; } // Second point of // intersection(x122, y122) x122 = (X1 + X2) / 2.0 + a * (X2 - X1) - b * (Y2 - Y1); y122 = (Y1 + Y2) / 2.0 + a * (Y2 - Y1) - b * (X1 - X2); // Check whether the point // of intersection lies // within circle 3 or not if (R3 >= Math.sqrt( (x122 - X3) * (x122 - X3) + (y122 - Y3) * (y122 - Y3))) { return true; } // Find the point of // intersection for // circle 1 & circle 3 a = (R1 * R1 - R3 * R3) / (2 * d13 * d13); b = Math.sqrt(2 * (R1 * R1 + R3 * R3) / (d13 * d13) - (R1 * R1 - R3 * R3) * (R1 * R1 - R3 * R3) / (Math.pow(d13, 4)) - 1) / 2; // First point of // intersection(x131, y131) x131 = (X1 + X3) / 2.0 + a * (X3 - X1) + b * (Y3 - Y1); y131 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) + b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.sqrt( (x131 - X2) * (x131 - X2) + (y131 - Y2) * (y131 - Y2))) { return true; } // Second point of // intersection(x132, y132) x132 = (X1 + X3) / 2.0 + a * (X3 - X1) - b * (Y3 - Y1); y132 = (Y1 + Y3) / 2.0 + a * (Y3 - Y1) - b * (X1 - X3); // Check whether the point // of intersection lies // within circle 2 or not if (R2 >= Math.sqrt( (x132 - X2) * (x132 - X2) + (y132 - Y2) * (y132 - Y2))) { return true; } // Find the point of // intersection for // circle 2 & circle 3 a = (R2 * R2 - R3 * R3) / (2 * d23 * d23); b = Math.sqrt(2 * (R2 * R2 + R3 * R3) / (d23 * d23) - (R2 * R2 - R3 * R3) * (R2 * R2 - R3 * R3) / (Math.pow(d23, 4)) - 1) / 2; // First point of // intersection(x231, y231) x231 = (X2 + X3) / 2.0 + a * (X3 - X2) + b * (Y3 - Y2); y231 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) + b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not if (R1 >= Math.sqrt( (x231 - X1) * (x231 - X1) + (y231 - Y1) * (y231 - Y1))) { return true; } // Second point of // intersection(x232, y232) x232 = (X2 + X3) / 2.0 + a * (X3 - X2) - b * (Y3 - Y2); y232 = (Y2 + Y3) / 2.0 + a * (Y3 - Y2) - b * (X2 - X3); // Check whether the point // of intersection lies // within circle 1 or not return R1 >= Math.sqrt( (x232 - X1) * (x232 - X1) + (y232 - Y1) * (y232 - Y1)); } }}// Function to check if there is// a common area between N// circlesfunction isGood(t, N, X, Y, V) { if (N >= 3) { // Check for a common area // for all combination // of 3 circles for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { for (let k = j + 1; k < N; k++) { // t * V give the // radius of the circle if (!intersection( X[i], Y[i], t * V[i], X[j], Y[j], t * V[j], X[k], Y[k], t * V[k])) return false; } } } return true; } // For N = 2 else { //(x2 - x1) ^ 2 + (y2 - y1) ^ 2 <= //(r1 + r2) ^ 2 for 2 circles // to intersect return Math.sqrt((X[0] - X[1]) * (X[0] - X[1]) + (Y[0] - Y[1]) * (Y[0] - Y[1])) <= t * (V[0] + V[1]); }}// Function to find minimum timefunction binarySearch(N, X, Y, V) { // Time depends on the area // of the 2D plane // Area =(Max(X) - Min(X))* // (Max(Y) - Min(Y)) let tl = 0.0, tu = 100000.0, t; // Number of iteration // depends on the precision for (let i = 0; i < 1000; i++) { t = (tl + tu) / 2.0; // If there is a common area // between N circles // for time t if (isGood(t, N, X, Y, V)) { tu = t; } // If there is no common area // between N circles // for time t else { tl = t; } } // Print the minimum time document.write(tu);}// Driver Codelet N = 4;let X = [1, -3, -1, 2];let Y = [2, 4, -2, -2];let V = [3, 2, 4, 5];// Function CallbinarySearch(N, X, Y, V);// This code is contributed by saurabh_jaiswal.</script> |
Output:
1.1157499537009508
Time Complexity: O(N3)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
