Dados dos círculos y una longitud, K. Encuentra si podemos unir dos puntos (uno en el perímetro de cada círculo), de modo que la distancia entre los puntos sea K. (Las coordenadas de ambos puntos no necesitan ser un valor entero).
Ejemplos:
Input: Circle-1 Center (0, 0) Radius = 5
Circle-2 Center (8, 3) Radius = 2
K = 3
Output: Yes
Maximum Distance: 15
Minimum Distance: 2
Acercarse:
- Tenemos que encontrar la distancia máxima y mínima posible entre dos puntos en estos círculos, si K se encuentra en este rango, la respuesta es sí, de lo contrario no podemos encontrar dicho segmento de línea.
- Para encontrar la distancia mínima y máxima:
- Caso 1: Cuando dos círculos no se cortan o simplemente se tocan en un punto.
En este escenario, la distancia máxima sería distancia entre centros + Radio (círculo 1) + Radio (círculo 2). La distancia mínima sería distancia entre centros – Radio (círculo 1) – Radio (círculo 2).
- Caso 2: Cuando los dos círculos se cortan exactamente en dos puntos.
En este escenario, la distancia máxima sería distancia entre centros + Radio (círculo 1) + Radio (círculo 2). La distancia mínima sería 0. (Tenemos dos puntos comunes en ambos círculos).
- Caso 3: Cuando el Círculo 1 está completamente dentro del Círculo 2.
En este escenario, la distancia máxima sería distancia entre centros + Radio (círculo 1) + Radio (círculo 2). La distancia mínima sería Radio (Círculo 2) – distancia entre centros – Radio (Círculo 1)
- Caso 4: Cuando el Círculo 2 está completamente dentro del Círculo 1.
En este escenario, la distancia máxima sería distancia entre centros + Radio (círculo 1) + Radio (círculo 2). La distancia mínima sería Radio (Círculo 1) – distancia entre centros – Radio (Círculo 2)
- Caso 5: Cuando ambos Círculos tienen el mismo centro
- Subcaso 1: el radio también es el mismo. Tanto la distancia mínima como la distancia máxima son 0.
- Subcaso 2: el radio es diferente (R1<R2)
La distancia máxima es R1+R2
La distancia mínima es R2-R1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement above approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
struct t {
ll x, y, r;
};
typedef struct t node;
// Return distance between the centers
long double dis(ll x1, ll y1, ll x2, ll y2)
{
return sqrt((x1 - x2) * (x1 - x2)
+ (y1 - y2) * (y1 - y2));
}
bool check(node c1, node c2, int k)
{
long double min = 0;
long double max = 0;
// Distance between centers
long double de = dis(c1.x, c1.y, c2.x, c2.y);
// Case 5
if (de == 0) {
// SubCase 1
if (c1.r == c2.r) {
min = 0;
max = 0;
}
// Subcase 2
else {
if (c1.r - c2.r > 0) {
min = c1.r - c2.r;
max = min + 2 * c2.r;
}
else {
min = c2.r - c1.r;
max = min + 2 * c1.r;
}
}
}
// Case 1
else if (de >= c1.r + c2.r) {
min = de - c1.r - c2.r;
max = de + c1.r + c2.r;
}
// Case 3
else if (de + c2.r < c1.r) {
max = c2.r + c1.r + de;
min = c1.r - de - c2.r;
}
// Case 4
else if (de + c1.r < c2.r) {
max = c2.r + c1.r + de;
min = c2.r - de - c1.r;
}
// Case 2
else if ((de + c2.r >= c1.r) || (de + c1.r >= c2.r)) {
max = c2.r + c1.r + de;
min = 0;
}
// Since value of k will always be an integer
ll temin = (ll)(ceil(min));
ll re = (ll)max;
if (k >= temin && k <= re)
return true;
return false;
}
// Driver Code
int main()
{
node circle1, circle2;
int k = 3;
circle1.x = 0;
circle1.y = 0;
circle1.r = 5;
circle2.x = 8;
circle2.y = 3;
circle2.r = 2;
if (check(circle1, circle2, k))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
Java
// Java program to implement above approach
class GFG
{
static class node
{
long x, y, r;
};
// Return distance between the centers
static long dis(long x1, long y1, long x2, long y2)
{
return (long) Math.sqrt((x1 - x2) * (x1 - x2)
+ (y1 - y2) * (y1 - y2));
}
static boolean check(node c1, node c2, int k)
{
long min = 0;
long max = 0;
// Distance between centers
long de = dis(c1.x, c1.y, c2.x, c2.y);
// Case 5
if (de == 0)
{
// SubCase 1
if (c1.r == c2.r)
{
min = 0;
max = 0;
}
// Subcase 2
else if (c1.r - c2.r > 0)
{
min = c1.r - c2.r;
max = min + 2 * c2.r;
}
else
{
min = c2.r - c1.r;
max = min + 2 * c1.r;
}
}
// Case 1
else if (de >= c1.r + c2.r)
{
min = de - c1.r - c2.r;
max = de + c1.r + c2.r;
}
// Case 3
else if (de + c2.r < c1.r)
{
max = c2.r + c1.r + de;
min = c1.r - de - c2.r;
}
// Case 4
else if (de + c1.r < c2.r)
{
max = c2.r + c1.r + de;
min = c2.r - de - c1.r;
}
// Case 2
else if ((de + c2.r >= c1.r) || (de + c1.r >= c2.r))
{
max = c2.r + c1.r + de;
min = 0;
}
// Since value of k will always be an integer
long temin = (long) (Math.ceil(min));
long re = (long) max;
if (k >= temin && k <= re)
{
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
node circle1 = new node();
node circle2 = new node();
int k = 3;
circle1.x = 0;
circle1.y = 0;
circle1.r = 5;
circle2.x = 8;
circle2.y = 3;
circle2.r = 2;
if (check(circle1, circle2, k))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by Princi Singh
Python
# Python3 program to implement above approach
from math import sqrt,ceil,floor
# Return distance between the centers
def dis(x1, y1, x2, y2):
return sqrt((x1 - x2) * (x1 - x2) +
(y1 - y2) * (y1 - y2))
def check(c1, c2, k):
min = 0
max = 0
# Distance between centers
de = dis(c1[0], c1[1], c2[0], c2[1])
# Case 5
if (de == 0):
# SubCase 1
if (c1[2] == c2[2]):
min = 0
max = 0
# Subcase 2
else:
if (c1[2] - c2[2] > 0):
min = c1[2] - c2[2]
max = min + 2 * c2[2]
else:
min = c2[2] - c1[2]
max = min + 2 * c1[2]
# Case 1
elif (de >= c1[2] + c2[2]):
min = de - c1[2] - c2[2]
max = de + c1[2] + c2[2]
# Case 3
elif (de + c2[2] < c1[2]):
max = c2[2] + c1[2] + de
min = c1[2] - de - c2[2]
# Case 4
elif (de + c1[2] < c2[2]):
max = c2[2] + c1[2] + de
min = c2[2] - de - c1[2]
# Case 2
elif ((de + c2[2] >= c1[2]) or (de + c1[2] >= c2[2])):
max = c2[2] + c1[2] + de
min = 0
# Since value of k wialways be an integer
temin = ceil(min)
re = max
if (k >= temin and k <= re):
return True
return False
# Driver Code
circle1 = [0, 0, 5]
circle2 = [8, 3, 2]
k = 3
if (check(circle1, circle2, k)):
print("YES")
else:
print("NO" )
# This code is contributed by mohit kumar 29
C#
// C# program to implement above approach
using System;
class GFG
{
public class node
{
public long x, y, r;
};
// Return distance between the centers
static long dis(long x1, long y1, long x2, long y2)
{
return (long) Math.Sqrt((x1 - x2) * (x1 - x2)
+ (y1 - y2) * (y1 - y2));
}
static Boolean check(node c1, node c2, int k)
{
long min = 0;
long max = 0;
// Distance between centers
long de = dis(c1.x, c1.y, c2.x, c2.y);
// Case 5
if (de == 0)
{
// SubCase 1
if (c1.r == c2.r)
{
min = 0;
max = 0;
}
// Subcase 2
else if (c1.r - c2.r > 0)
{
min = c1.r - c2.r;
max = min + 2 * c2.r;
}
else
{
min = c2.r - c1.r;
max = min + 2 * c1.r;
}
}
// Case 1
else if (de >= c1.r + c2.r)
{
min = de - c1.r - c2.r;
max = de + c1.r + c2.r;
}
// Case 3
else if (de + c2.r < c1.r)
{
max = c2.r + c1.r + de;
min = c1.r - de - c2.r;
}
// Case 4
else if (de + c1.r < c2.r)
{
max = c2.r + c1.r + de;
min = c2.r - de - c1.r;
}
// Case 2
else if ((de + c2.r >= c1.r) || (de + c1.r >= c2.r))
{
max = c2.r + c1.r + de;
min = 0;
}
// Since value of k will always be an integer
long temin = (long) (Math.Ceiling((double)min));
long re = (long) max;
if (k >= temin && k <= re)
{
return true;
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
node circle1 = new node();
node circle2 = new node();
int k = 3;
circle1.x = 0;
circle1.y = 0;
circle1.r = 5;
circle2.x = 8;
circle2.y = 3;
circle2.r = 2;
if (check(circle1, circle2, k))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to implement above approach
// Return distance between the centers
function dis(x1,y1,x2,y2)
{
return Math.sqrt((x1 - x2) * (x1 - x2)
+ (y1 - y2) * (y1 - y2));
}
function check(c1,c2,k)
{
let min = 0;
let max = 0;
// Distance between centers
let de = dis(c1[0], c1[1], c2[0], c2[1]);
// Case 5
if (de == 0)
{
// SubCase 1
if (c1[2] == c2[2])
{
min = 0;
max = 0;
}
// Subcase 2
else if (c1[2] - c2[2] > 0)
{
min = c1[2] - c2[2];
max = min + 2 * c2[2];
}
else
{
min = c2[2] - c1[2];
max = min + 2 * c1[2];
}
}
// Case 1
else if (de >= c1[2] + c2[2])
{
min = de - c1[2] - c2[2];
max = de + c1[2] + c2[2];
}
// Case 3
else if (de + c2[2] < c1[2])
{
max = c2[2] + c1[2] + de;
min = c1[2] - de - c2[2];
}
// Case 4
else if (de + c1[2] < c2[2])
{
max = c2[2] + c1[2] + de;
min = c2[2]- de - c1[2];
}
// Case 2
else if ((de + c2[2] >= c1[2]) ||
(de + c1[2] >= c2[2]))
{
max = c2[2] + c1[2] + de;
min = 0;
}
// Since value of k will always be an integer
let temin = (Math.ceil(min));
let re = max;
if (k >= temin && k <= re)
{
return true;
}
return false;
}
// Driver Code
let circle1 = [0, 0, 5];
let circle2 = [8, 3, 2];
let k = 3;
if (check(circle1, circle2, k))
{
document.write("YES");
}
else
{
document.write("NO");
}
// This code is contributed by unknown2108
</script>
Producción:
YES
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)