Radio de la circunferencia inscrita dentro de tres circunferencias tangentes

Hay 4 círculos con radio entero positivo r1 , r2 , r3 y r4 como se muestra en la siguiente figura.

La tarea es encontrar el radio r4 del círculo formado por tres círculos cuando se dan los radios r1 , r2 , r3 .
(Tenga en cuenta que los círculos en la imagen de arriba son tangentes entre sí).

Ejemplos:

Entrada: r1 = 1, r2 = 1, r3 = 1
Salida: 0,154701

Entrada: r1 = 23, r2 = 46, r3 = 69
Salida: 6,000000

Enfoque 1: (usando la búsqueda binaria ):

La política es unir los centros de todos los círculos y formar 4 triángulos.
Después de formar los triángulos, iguale la suma de las áreas de los tres triángulos más pequeños con el triángulo principal en la medida de lo posible mediante la búsqueda binaria.

Análisis del enfoque mencionado:

Este método funciona porque inicialmente hay 4 triángulos como se indica en la imagen de arriba.
El triángulo principal con lados $(r1+r2, r1+r3, r2+r3)$ y los tres triángulos más pequeños con lados $(r1+r4, r2+r4, r1+r2), (r1+r4, r3+r4, r1+r3), (r2+r4, r3+r4, r2+r3)$ .
El triángulo principal consta de los pequeños, por lo que el área del triángulo principal es la suma de las áreas de los más pequeños.

Formando un espacio de búsqueda:
Aquí búsqueda binaria . Se puede elegir el valor de r y se puede calcular la suma de las áreas de los tres triángulos más pequeños y compararla con el área del triángulo principal.

Elección del límite inferior $l = 0$
Elección del límite superior $h = s/(r1 + r2 + r3)$

Por intuición, el valor del límite superior para r4 como el radio del círculo inscrito en el $(r1+r2, r1+r3, r2+r3)$ triángulo es menor que:
r _{upper_bound} $= 2s/(r1+r2+r2+r3+r3+r1) = s/(r1+r2+r3)$
Ahora la búsqueda binaria se puede aplicar en el siguiente espacio de búsqueda.

A continuación se muestra la implementación del problema utilizando el enfoque anterior.

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Radius of the 3 given circles
// declared as double.
double r1, r2, r3;
 
// Calculation of area of a triangle by Heron's formula
double area(double a, double b, double c)
{
    double p = (a + b + c) / 2;
    return sqrt(p) * sqrt(p - a) * sqrt(p - b) * sqrt(p - c);
}
 
// Applying binary search to find the
// radius r4 of the required circle
double binary_search()
{
    // Area of main triangle
    double s = area(r1 + r2, r2 + r3, r3 + r1);
    double l = 0, h = s / (r1 + r2 + r3);
    // Loop runs until l and h becomes approximately equal
    while (h - l >= 1.e-7) {
        double mid = (l + h) / 2;
 
        // Area of smaller triangles
        double s1 = area(mid + r1, mid + r2, r1 + r2);
        double s2 = area(mid + r1, mid + r3, r1 + r3);
        double s3 = area(mid + r2, mid + r3, r2 + r3);
 
        // If sum of smaller triangles
        // is less than main triangle
        if (s1 + s2 + s3 < s) {
            l = mid;
        }
        // If sum of smaller triangles is
        // greater than or equal to main triangle
        else {
            h = mid;
        }
    }
    return (l + h) / 2;
}
// Driver code
int main()
{
    // Taking r1, r2, r3 as input
    r1 = 1.0;
    r2 = 2.0;
    r3 = 3.0;
    // Call to function binary search
    cout << fixed << setprecision(6) << binary_search() << endl;
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Radius of the 3 given circles
    // declared as double.
    static double r1, r2, r3;
 
    // Calculation of area of a triangle by Heron's formula
    static double area(double a, double b, double c)
    {
        double p = (a + b + c) / 2;
        return Math.sqrt(p) * Math.sqrt(p - a) *
               Math.sqrt(p - b) * Math.sqrt(p - c);
    }
 
    // Applying binary search to find the
    // radius r4 of the required circle
    static double binary_search()
    {
        // Area of main triangle
        double s = area(r1 + r2, r2 + r3, r3 + r1);
        double l = 0, h = s / (r1 + r2 + r3);
         
        // Loop runs until l and h becomes approximately equal
        while (h - l >= 1.e-7)
        {
            double mid = (l + h) / 2;
 
            // Area of smaller triangles
            double s1 = area(mid + r1, mid + r2, r1 + r2);
            double s2 = area(mid + r1, mid + r3, r1 + r3);
            double s3 = area(mid + r2, mid + r3, r2 + r3);
 
            // If sum of smaller triangles
            // is less than main triangle
            if (s1 + s2 + s3 < s)
            {
                l = mid;
            }
             
            // If sum of smaller triangles is
            // greater than or equal to main triangle
            else
            {
                h = mid;
            }
        }
        return (l + h) / 2;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Taking r1, r2, r3 as input
        r1 = 1.0;
        r2 = 2.0;
        r3 = 3.0;
         
        // Call to function binary search
        System.out.printf("%.6f", binary_search());
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
import math
 
# Radius of the 3 given circles
r1 = 0
r2 = 0
r3 = 0
 
# Calculation of area of a
# triangle by Heron's formula
def area(a, b, c):
     
    p = (a + b + c) / 2
 
    return ((math.sqrt(p)) *
            (math.sqrt(p - a)) *
            (math.sqrt(p - b)) *
            (math.sqrt(p - c)))
 
# Applying binary search to find the
# radius r4 of the required circle
def binary_search():
     
    global r1, r2, r3
 
    # Area of main triangle
    s = area(r1 + r2, r2 + r3, r3 + r1)
    l = 0
    h = s / (r1 + r2 + r3)
 
    # Loop runs until l and h
    # becomes approximately equal
    while (h - l > 0.00000001):
        mid = (l + h) / 2
 
        # Area of smaller triangles
        s1 = area(mid + r1, mid + r2, r1 + r2)
        s2 = area(mid + r1, mid + r3, r1 + r3)
        s3 = area(mid + r2, mid + r3, r2 + r3)
 
        # If sum of smaller triangles
        # is less than main triangle
        if (s1 + s2 + s3 < s):
            l = mid
             
        # If sum of smaller triangles is
        # greater than or equal to main triangle
        else:
            h = mid
             
    return ((l + h) / 2)
 
# Driver code
 
# Taking r1, r2, r3 as input
r1 = 1
r2 = 2
r3 = 3
 
# Call to function binary search
print("{0:.6f}".format(binary_search()))
 
# This code is contributed by avanitrachhadiya2155

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Radius of the 3 given circles
    // declared as double.
    static double r1, r2, r3;
 
    // Calculation of area of a triangle by Heron's formula
    static double area(double a, double b, double c)
    {
        double p = (a + b + c) / 2;
        return Math.Sqrt(p) * Math.Sqrt(p - a) *
            Math.Sqrt(p - b) * Math.Sqrt(p - c);
    }
 
    // Applying binary search to find the
    // radius r4 of the required circle
    static double binary_search()
    {
        // Area of main triangle
        double s = area(r1 + r2, r2 + r3, r3 + r1);
        double l = 0, h = s / (r1 + r2 + r3);
         
        // Loop runs until l and h
        // becomes approximately equal
        while (h - l > 0.00000001)
        {
            double mid = (l + h) / 2;
 
            // Area of smaller triangles
            double s1 = area(mid + r1, mid + r2, r1 + r2);
            double s2 = area(mid + r1, mid + r3, r1 + r3);
            double s3 = area(mid + r2, mid + r3, r2 + r3);
 
            // If sum of smaller triangles
            // is less than main triangle
            if (s1 + s2 + s3 < s)
            {
                l = mid;
            }
             
            // If sum of smaller triangles is
            // greater than or equal to main triangle
            else
            {
                h = mid;
            }
        }
        return (l + h) / 2;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Taking r1, r2, r3 as input
        r1 = 1.0;
        r2 = 2.0;
        r3 = 3.0;
         
        // Call to function binary search
        Console.Write("{0:F6}", binary_search());
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript implementation of the approach
 
// Radius of the 3 given circles
// declared as double.
let r1, r2, r3;
 
// Calculation of area of a triangle
// by Heron's formula
function area(a, b, c)
{
    let p = (a + b + c) / 2;
    return Math.sqrt(p) * Math.sqrt(p - a) *
       Math.sqrt(p - b) * Math.sqrt(p - c);
}
 
// Applying binary search to find the
// radius r4 of the required circle
function binary_search()
{
     
    // Area of main triangle
    let s = area(r1 + r2, r2 + r3, r3 + r1);
    let l = 0, h = s / (r1 + r2 + r3);
     
    // Loop runs until l and h
    // becomes approximately equal
    while (h - l >= 1.e-7)
    {
        let mid = (l + h) / 2;
 
        // Area of smaller triangles
        let s1 = area(mid + r1, mid + r2, r1 + r2);
        let s2 = area(mid + r1, mid + r3, r1 + r3);
        let s3 = area(mid + r2, mid + r3, r2 + r3);
 
        // If sum of smaller triangles
        // is less than main triangle
        if (s1 + s2 + s3 < s)
        {
            l = mid;
        }
         
        // If sum of smaller triangles is
        // greater than or equal to main triangle
        else
        {
            h = mid;
        }
    }
    return (l + h) / 2;
}
 
// Driver code
 
// Taking r1, r2, r3 as input
r1 = 1.0;
r2 = 2.0;
r3 = 3.0;
 
// Call to function binary search
document.write(binary_search().toPrecision(6));
 
// This code is contributed by subhammahato348
 
</script>

Producción:

0.260870

Complejidad de tiempo: O (logn)

Espacio Auxiliar: O(1)

Enfoque 2: (usando el teorema de Descartes)

Según el Teorema de Descartes, los recíprocos de los radios, o “curvaturas”, de estos círculos $k_1 = 1/r_1, k_2 = 1/r_2, k_3 = 1/r_3\:and\:k_4 = 1/r_4$ satisfacen la siguiente relación.
$2(k_1^2+k_2^2+k_3^2+k_4^2) = (k_1+k_2+k_3+k_4)^2$
Si $k_1, k_2, k_3$ se conocen, se puede resolver para, $k_4 = k_1 + k_2 + k_3 \pm 2\sqrt{k_1 k_2 + k_2 k_3 + k_1 k_3}$
Al resolver la ecuación anterior;
$r_4 = (r_1*r_2*r_3)\, /\, (r_1*r_2 + r_2*r_3 + r_3*r_1 + 2.0\, *\, \sqrt{(r_1*r_2*r_3*(r_1+r_2+r_3))})$

A continuación se muestra la implementación del problema utilizando la fórmula anterior.

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Driver code
int main()
{
    // Radius of the 3 given circles declared as double.
    double r1, r2, r3;
 
    // Taking r1, r2, r3 as input
    r1 = 1;
    r2 = 2;
    r3 = 3;
 
    // Calculation of r4 using formula given above
    double r4 = (r1 * r2 * r3)
                / (r1 * r2 + r2 * r3 + r1 * r3
                   + 2.0 * sqrt(r1 * r2 * r3 * (r1 + r2 + r3)));
    cout << fixed << setprecision(6) << r4 << '\n';
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
 
    // Driver code
    public static void main(String[] args)
    {
        // Radius of the 3 given circles declared as double.
        double r1, r2, r3;
 
        // Taking r1, r2, r3 as input
        r1 = 1;
        r2 = 2;
        r3 = 3;
 
        // Calculation of r4 using formula given above
        double r4 = (r1 * r2 * r3) /
                    (r1 * r2 + r2 * r3 + r1 * r3 + 2.0 *
                    Math.sqrt(r1 * r2 * r3 * (r1 + r2 + r3)));
        System.out.printf("%.6f", r4);
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
from math import sqrt
 
# Driver code
 
# Radius of the 3 given circles declared as double.
 
# Taking r1, r2, r3 as input
r1 = 1
r2 = 2
r3 = 3
 
# Calculation of r4 using formula given above
r4 = (r1 * r2 * r3)/ (r1 * r2 + r2 * r3 + r1 * r3
            + 2.0 * sqrt(r1 * r2 * r3 * (r1 + r2 + r3)))
print(round(r4, 6))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
  
    // Driver code
    public static void Main(String[] args)
    {
        // Radius of the 3 given circles declared as double.
        double r1, r2, r3;
  
        // Taking r1, r2, r3 as input
        r1 = 1;
        r2 = 2;
        r3 = 3;
  
        // Calculation of r4 using formula given above
        double r4 = (r1 * r2 * r3) /
                    (r1 * r2 + r2 * r3 + r1 * r3 + 2.0 *
                    Math.Sqrt(r1 * r2 * r3 * (r1 + r2 + r3)));
        Console.Write("{0:F6}", r4);
    }
}
 
// This code contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript implementation of the approach
 
// Driver code
 
// Radius of the 3 given circles
// declared as double.
let r1, r2, r3;
 
// Taking r1, r2, r3 as input
r1 = 1;
r2 = 2;
r3 = 3;
 
// Calculation of r4 using formula given above
let r4 = (r1 * r2 * r3) / (r1 * r2 + r2 *
          r3 + r1 * r3 + 2.0 * Math.sqrt(
          r1 * r2 * r3 * (r1 + r2 + r3)));
 
document.write(r4.toFixed(6) + "<br>");
 
// This code is contributed by souravmahato348
 
</script>

Producción:

0.260870

Complejidad de tiempo : O (logn)

Espacio Auxiliar: O(1)

Referencia :

Publicación traducida automáticamente

Artículo escrito por saintpopo y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta