Dados los centros y los radios de tres círculos A , B y C en forma de {X, Y, R} , donde (X, Y) es el centro del círculo y R es el radio de ese círculo . La tarea es verificar si dos círculos se intersecan de manera que el tercer círculo pase por los puntos de intersección y los centros de los dos círculos . Si se encuentra que es cierto , escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: A = {0, 0, 8}, B = {0, 10, 6}, C = {0, 5, 5}
Salida : SíEntrada: arr[] = {{5, 0, 5}, {15, 0, 2}, {20, 0, 1}}
Salida: No
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Supongamos que C1C2 , C1C3 y C2C3 son la distancia entre el centro del círculo C1 y C2 , C1 y C3 , y C2 y C3 respectivamente .
- Entonces los círculos C1 y C2 se cortan si C1C2 < r1 + r2 .
- Ahora, dado que el tercer círculo debe pasar por el centro de los dos círculos y sus puntos de intersección, la línea que pasa por C1 y C2 se convierte en la bisectriz perpendicular de la cuerda S1S2 , como se muestra en la figura.
- Entonces se puede observar que ahora C1C3 es igual a C3C2 y C1C3 es el radio del tercer círculo y el centro del tercer círculo es el punto medio de C1 y C2 .
- Por lo tanto, los tres círculos dados satisfacen los criterios dados si y solo si el centro de C3 se convierte en el punto medio de C1 y C2 y si C1 y C2 se intersecan y el radio de C3 se convierte en la mitad de C1C2 .
Siga los pasos a continuación para resolver el problema:
- Genere cada combinación de los tres círculos dados y realice los siguientes pasos:
- Encuentra la distancia entre el centro de los primeros dos círculos y guárdala en una variable, digamos C1C2 .
- Si C1C2 es menor que la suma de los radios de los dos primeros círculos y el centro del tercer círculo es el punto medio de los centros de los dos primeros círculos, entonces escriba «Sí» .
- Después de completar los pasos anteriores, si no existe ninguna combinación de círculos que satisfaga los criterios dados, imprima «No» .
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;
// Structure of the circle
class circle {
public:
double x;
double y;
double r;
};
//Utility function to check if given
// circles satisfy required criteria
bool check(circle C[])
{
// Stores the distance between
// the centres of C1 and C2
double C1C2
= sqrt((C[1].x - C[0].x)
* (C[1].x - C[0].x)
+ (C[1].y - C[0].y)
* (C[1].y - C[0].y));
// Stores the status if the given
// given criteria is satisfied or not
bool flag = 0;
// If C1C2 is less than the sum of
// the radii of the first 2 circles
if (C1C2 < (C[0].r + C[1].r)) {
// If C3 is the midpoint of
// the centres at C1 and C2
if ((C[0].x + C[1].x)
== 2 * C[2].x
&& (C[0].y + C[1].y)
== 2 * C[2].y) {
// Mark flag true
flag = 1;
}
}
// Return flag
return flag;
}
// Function to check if the given
// circles satisfy required criteria
bool IsFairTriplet(circle c[])
{
bool f = false;
// Check for the current
// combination of circles
f |= check(c);
for (int i = 0; i < 2; i++) {
swap(c[0], c[2]);
// Check for the next
// combination
f |= check(c);
}
return f;
}
// Driver Code
int main()
{
circle C[3];
C[0] = { 0, 0, 8 };
C[1] = { 0, 10, 6 };
C[2] = { 0, 5, 5 };
if (IsFairTriplet(C))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java approach for the above approach
class GFG{
// Structure of the circle
static class circle
{
double x;
double y;
double r;
public circle(int x, int y, int r)
{
this.x = x;
this.y = y;
this.r = r;
}
}
// Utility function to check if given
// circles satisfy required criteria
static boolean check(circle C[])
{
// Stores the distance between
// the centres of C1 and C2
double C1C2 = Math.sqrt(
(C[1].x - C[0].x) * (C[1].x - C[0].x) +
(C[1].y - C[0].y) * (C[1].y - C[0].y));
// Stores the status if the given
// given criteria is satisfied or not
boolean flag = false;
// If C1C2 is less than the sum of
// the radii of the first 2 circles
if (C1C2 < (C[0].r + C[1].r))
{
// If C3 is the midpoint of
// the centres at C1 and C2
if ((C[0].x + C[1].x) == 2 * C[2].x &&
(C[0].y + C[1].y) == 2 * C[2].y)
{
// Mark flag true
flag = true;
}
}
// Return flag
return flag;
}
// Function to check if the given
// circles satisfy required criteria
static boolean IsFairTriplet(circle c[])
{
boolean f = false;
// Check for the current
// combination of circles
f |= check(c);
for(int i = 0; i < 2; i++)
{
swap(c[0], c[2]);
// Check for the next
// combination
f |= check(c);
}
return f;
}
static void swap(circle circle1, circle circle2)
{
circle temp = circle1;
circle1 = circle2;
circle2 = temp;
}
// Driver Code
public static void main(String[] args)
{
circle C[] = new circle[3];
C[0] = new circle(0, 0, 8);
C[1] = new circle(0, 10, 6);
C[2] = new circle(0, 5, 5);
if (IsFairTriplet(C))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by abhinavjain194
Python3
# Python3 program for the above approach
from math import sqrt
# Structure of the circle
class circle:
def __init__(self, a, b, c):
self.x = a
self.y = b
self.r = c
# Utility function to check if given
# circles satisfy required criteria
def check(C):
# Stores the distance between
# the centres of C1 and C2
C1C2 = sqrt((C[1].x - C[0].x)
* (C[1].x - C[0].x)
+ (C[1].y - C[0].y)
* (C[1].y - C[0].y))
# Stores the status if the given
# given criteria is satisfied or not
flag = 0
# If C1C2 is less than the sum of
# the radii of the first 2 circles
if (C1C2 < (C[0].r + C[1].r)):
# If C3 is the midpoint of
# the centres at C1 and C2
if ((C[0].x + C[1].x) == 2 * C[2].x and (C[0].y + C[1].y) == 2 * C[2].y):
# Mark flag true
flag = 1
# Return flag
return flag
# Function to check if the given
# circles satisfy required criteria
def IsFairTriplet(c):
f = False
# Check for the current
# combination of circles
f |= check(c)
for i in range(2):
c[0], c[2] = c[2], c[0]
# Check for the next
# combination
f |= check(c)
return f
# Driver Code
if __name__ == '__main__':
C = [circle(0,0,0) for i in range(3)]
C[0] = circle(0, 0, 8)
C[1] = circle(0, 10, 6)
C[2] = circle(0, 5, 5)
if (IsFairTriplet(C)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29.
C#
// C# approach for the above approach
using System;
class GFG{
// Structure of the circle
class circle
{
public double x;
public double y;
public double r;
public circle(int x, int y, int r)
{
this.x = x;
this.y = y;
this.r = r;
}
}
// Utility function to check if given
// circles satisfy required criteria
static bool check(circle []C)
{
// Stores the distance between
// the centres of C1 and C2
double C1C2 = Math.Sqrt(
(C[1].x - C[0].x) * (C[1].x - C[0].x) +
(C[1].y - C[0].y) * (C[1].y - C[0].y));
// Stores the status if the given
// given criteria is satisfied or not
bool flag = false;
// If C1C2 is less than the sum of
// the radii of the first 2 circles
if (C1C2 < (C[0].r + C[1].r))
{
// If C3 is the midpoint of
// the centres at C1 and C2
if ((C[0].x + C[1].x) == 2 * C[2].x &&
(C[0].y + C[1].y) == 2 * C[2].y)
{
// Mark flag true
flag = true;
}
}
// Return flag
return flag;
}
// Function to check if the given
// circles satisfy required criteria
static bool IsFairTriplet(circle []c)
{
bool f = false;
// Check for the current
// combination of circles
f |= check(c);
for(int i = 0; i < 2; i++)
{
swap(c[0], c[2]);
// Check for the next
// combination
f |= check(c);
}
return f;
}
static void swap(circle circle1, circle circle2)
{
circle temp = circle1;
circle1 = circle2;
circle2 = temp;
}
// Driver Code
public static void Main(String[] args)
{
circle []C = new circle[3];
C[0] = new circle(0, 0, 8);
C[1] = new circle(0, 10, 6);
C[2] = new circle(0, 5, 5);
if (IsFairTriplet(C))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript approach for the above approach
// Structure of the circle
class circle
{
constructor(x,y,r)
{
this.x = x;
this.y = y;
this.r = r;
}
}
// Utility function to check if given
// circles satisfy required criteria
function check(C)
{
// Stores the distance between
// the centres of C1 and C2
let C1C2 = Math.sqrt(
(C[1].x - C[0].x) * (C[1].x - C[0].x) +
(C[1].y - C[0].y) * (C[1].y - C[0].y));
// Stores the status if the given
// given criteria is satisfied or not
let flag = false;
// If C1C2 is less than the sum of
// the radii of the first 2 circles
if (C1C2 < (C[0].r + C[1].r))
{
// If C3 is the midpoint of
// the centres at C1 and C2
if ((C[0].x + C[1].x) == 2 * C[2].x &&
(C[0].y + C[1].y) == 2 * C[2].y)
{
// Mark flag true
flag = true;
}
}
// Return flag
return flag;
}
// Function to check if the given
// circles satisfy required criteria
function IsFairTriplet(c)
{
let f = false;
// Check for the current
// combination of circles
f |= check(c);
for(let i = 0; i < 2; i++)
{
swap(c[0], c[2]);
// Check for the next
// combination
f |= check(c);
}
return f;
}
function swap(circle1,circle2)
{
let temp = circle1;
circle1 = circle2;
circle2 = temp;
}
// Driver Code
let C=new Array(3);
C[0] = new circle(0, 0, 8);
C[1] = new circle(0, 10, 6);
C[2] = new circle(0, 5, 5);
if (IsFairTriplet(C))
document.write("Yes");
else
document.write("No");
// This code is contributed by unknown2108
</script>
Producción:
Yes
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA