Dada una array arr[][] de tamaño N , que consta de pares de coordenadas tales que arr[i][0] y arr[i][1] representan las coordenadas X e Y en un plano 2D. Dada otra array V[] que denota la velocidad máxima de cada punto en cualquier dirección, la tarea es encontrar el tiempo mínimo para que todos los puntos dados se encuentren en cualquier punto arbitrario en el plano 2D.
Ejemplos:
Entrada: N = 4, arr[][] = {{1, 2}, {-3, 34}, {-1, -2}, {2, -2}}, V[] = {3, 2 , 4, 5}
Salida: 1.1157499537009508Entrada: N = 2, arr[][] = {{1. 2}, {-1, -2}}, V[] = {2, 3}
Salida: 0,8944271909999159
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Los N puntos dados en el eje de coordenadas pueden moverse en cualquier dirección y si se permite que estos puntos se muevan durante T tiempo, entonces pueden alcanzar cualquier punto dentro del círculo (reduciendo V[i] en consecuencia) que tenga un radio igual a V[i ] * T y centro igual a la posición inicial del punto, donde V[i] representa la velocidad del i -ésimo punto .
- Por lo tanto, para minimizar el área común de estos N círculos, el radio debe minimizarse y si existe un punto de encuentro común en el tiempo T , entonces debe existir un punto de encuentro para T’ > T , ya que habrá un área más común para T’ .
- Por tanto, la idea es comprobar la existencia de un punto de encuentro común, es decir, comprobar la existencia de un área común de N círculos .
- A continuación se muestra la ilustración de todas las combinaciones posibles de 3 círculos y cada uno tiene un área de intersección distinta de cero, entonces todos los 3 círculos tienen un área de intersección común como:
- En las Fig. 1, 2, 3, 4, 5, la suma del radio de dos de los tres círculos es menor que la distancia entre ellos, lo que significa que no hay un área común entre los tres círculos.
- En las figuras 6, 7, 8, 9, uno o dos círculos se encuentran dentro de otro círculo.
- En las figuras 10, 11, 12, 13 encuentre la intersección entre dos círculos y verifique si esos puntos de intersección se encuentran dentro del otro círculo o no.
A partir de las observaciones anteriores, la idea es utilizar la búsqueda binaria para encontrar el tiempo mínimo con un único punto de intersección para todos los N puntos dados . Siga los pasos a continuación para resolver el problema dado:
- Declare una función, digamos intersección (X1, Y1, R1, X2, Y2, R2, X3, Y3, R3) que tome las coordenadas y el radio de los círculos como parámetro y realice los siguientes pasos:
- Si la suma de los radios de dos círculos cualesquiera es menor que la suma de las distancias entre sus centros, entonces devuelve falso ya que no existe tal área común entre ellos.
- Ahora, verifique si dos círculos tienen un área común o no . Si se encuentra que es verdadero , entonces devuelve verdadero . De lo contrario, devuelve falso .
- Declare una función , digamos isGood(mid, N, X, Y, V) que tome el tiempo posible actual, las coordenadas de los N puntos y la velocidad de cada punto como parámetro y realice los siguientes pasos:
- Si el valor de N es al menos 3 , compruebe todas las combinaciones posibles de tres círculos para obtener el área común llamando a la función intersección (X1, Y1, R1, X2, Y2, R2, X3, Y3, R3) . Si existe una combinación de este tipo que no tiene un área común, devuelve false . De lo contrario, devuelve verdadero .
- Si el valor de N es 2 , compruebe si los dos círculos tienen un área común o no . Si se encuentra que es verdadero , entonces devuelve verdadero . De lo contrario, devuelve falso .
- Inicialice dos variables, digamos tl como 0.0 y tu como 100000.0 como el tiempo mínimo y máximo requerido para obtener el único punto de intersección respectivamente.
- Ahora, itere sobre el rango [0, 1000] para obtener la mejor precisión del tiempo resultante y realice una búsqueda binaria siguiendo los pasos a continuación:
- Encuentre el valor medio, digamos mid como (tl + tu)/2.0 .
- Ahora verifique si el tiempo medio anterior tiene al menos un área común de intersecciones o no llamando a la función isGood(mid, N, X, Y, V) . Si se determina que es cierto , actualice tu como mid . De lo contrario, actualice tl como t .
- Después de completar los pasos anteriores, imprima el valor de tu como el tiempo mínimo resultante para todos los N puntos dados que se cruzan en un punto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check for common area
// between three circles
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 = 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
// circles
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]) == 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 time
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
cout << fixed << setprecision(16) << tu << endl;
}
// Driver Code
int 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 approach
class 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 approach import math # Function to check for common area # between three circles def 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 # circles def 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 time def 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 Code N = 4 X = [1, -3, -1, 2] Y = [2, 4, -2, -2] V = [3, 2, 4, 5] # Function Call binarySearch(N, X, Y, V) # This code is contributed by Gautam goel(gautamgoel962).
C#
// C# program for the above approach
using System;
class GFG{
// Function to check for common area
// between three circles
public 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
// circles
public 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 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
Console.WriteLine(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);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to check for common area
// between three circles
function 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
// circles
function 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 time
function 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 Code
let N = 4;
let X = [1, -3, -1, 2];
let Y = [2, 4, -2, -2];
let V = [3, 2, 4, 5];
// Function Call
binarySearch(N, X, Y, V);
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
1.1157499537009508
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por debarpan_bose_chowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA