Compruebe si algún par de semicírculos se cruzan o no

Dada una array arr[] que consta de N enteros tales que cada par de puntos (x, y) representa los extremos del semicírculo como (x, 0) y (y, 0) , la tarea es comprobar si algún par de semicírculos cruzarse o no. Si se encuentra que es cierto , escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {0, 15, 5, 10}
Salida: No

Entrada: arr[] = {0, 10, 5, 15}
Salida: Sí

Enfoque: el problema dado se puede resolver comprobando si algún par de semicírculos se cruzan o no y luego imprimiendo los elementos en consecuencia. Siga los pasos a continuación para resolver el problema:

• Almacena todos los semicírculos posibles en un vector con sus correspondientes coordenadas x e y .
• Ahora, genere todos los pares posibles de los vectores anteriores y realice los siguientes pasos:
  • Sea el par de coordenadas X e Y y verifique si los círculos se intersecan o no usando las siguientes condiciones:
    • Si el valor de (X[0] < Y[0] , X[1] < Y[1] e Y[0] < X[2]) o (Y[0] < X[0] , Y[1 ] < X[1] , y X[0] < Y[1]) , entonces el semicírculo se interseca. De lo contrario, no se cruza.
    • Si los dos círculos anteriores se cruzan, imprima «Sí» y salga del bucle .
• Después de completar los pasos anteriores, si algún par de círculos no se cruzan, escriba «No» .

// C++ program for the above approach
 
#include <iostream>
#include <vector>
using namespace std;
 
// Function to check if any pairs of
// the semicircles intersects or not
bool checkIntersection(int arr[], int N)
{
 
    // Stores the coordinates of all
    // the semicircles
    vector<pair<int, int> > vec;
 
    for (int i = 0; i < N - 1; i++) {
 
        // x and y are coordinates
        int x = arr[i], y = arr[i + 1];
 
        // Store the minimum and maximum
        // value of the pair
        int minn = min(x, y);
        int maxx = max(x, y);
 
        // Push the pair in vector
        vec.push_back({ minn, maxx });
    }
 
    // Compare one pair with other pairs
    for (int i = 0; i < vec.size(); i++) {
 
        pair<int, int> x = vec[i];
 
        // Generating the second pair
        for (int j = 0;
             j < vec.size(); j++) {
 
            // Extract all the second
            // pairs one by one
            pair<int, int> y = vec[j];
 
            // 1st condition
            bool cond1
                = (x.first < y.first
                   and x.second < y.second
                   and y.first < x.second);
 
            // 2nd condition
            bool cond2
                = (y.first < x.first
                   and y.second < x.second
                   and x.first < y.second);
 
            // If any one condition
            // is true
            if (cond1 or cond2) {
                return true;
            }
        }
    }
 
    // If any pair of semicircles
    // doesn't exists
    return false;
}
 
// Driver Code
int main()
{
    int arr[] = { 0, 15, 5, 10 };
    int N = sizeof(arr) / sizeof(int);
 
    if (checkIntersection(arr, N))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
static class pair
{
    int first, second;
     
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
 
// Function to check if any pairs of
// the semicircles intersects or not
static boolean checkIntersection(int arr[], int N)
{
 
    // Stores the coordinates of all
    // the semicircles
    Vector<pair > vec = new Vector<>();
 
    for(int i = 0; i < N - 1; i++)
    {
         
        // x and y are coordinates
        int x = arr[i], y = arr[i + 1];
 
        // Store the minimum and maximum
        // value of the pair
        int minn = Math.min(x, y);
        int maxx = Math.max(x, y);
 
        // Push the pair in vector
        vec.add(new pair( minn, maxx ));
    }
 
    // Compare one pair with other pairs
    for(int i = 0; i < vec.size(); i++)
    {
        pair x = vec.elementAt(i);
 
        // Generating the second pair
        for(int j = 0;
                j < vec.size(); j++)
        {
 
            // Extract all the second
            // pairs one by one
            pair y = vec.elementAt(j);
 
            // 1st condition
            boolean cond1 = (x.first < y.first &&
                            x.second < y.second &&
                             y.first < x.second);
 
            // 2nd condition
            boolean cond2 = (y.first < x.first &&
                            y.second < x.second &&
                             x.first < y.second);
 
            // If any one condition
            // is true
            if (cond1 || cond2)
            {
                return true;
            }
        }
    }
 
    // If any pair of semicircles
    // doesn't exists
    return false;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 0, 15, 5, 10 };
    int N = arr.length;
 
    if (checkIntersection(arr, N))
        System.out.print("Yes");
    else
        System.out.print("No");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to check if any pairs of
# the semicircles intersects or not
def checkIntersection(arr, N):
     
    # Stores the coordinates of all
    # the semicircles
    vec = []
 
    for i in range(N - 1):
         
        # x and y are coordinates
        x = arr[i]
        y = arr[i + 1]
 
        # Store the minimum and maximum
        # value of the pair
        minn = min(x, y)
        maxx = max(x, y)
 
        # Push the pair in vector
        vec.append([minn, maxx])
 
    # Compare one pair with other pairs
    for i in range(len(vec)):
        x = vec[i]
 
        # Generating the second pair
        for j in range(len(vec)):
             
            # Extract all the second
            # pairs one by one
            y = vec[j]
 
            # 1st condition
            cond1 = (x[0] < y[0] and
                     x[1] < y[1] and
                     y[0] < x[1])
 
            # 2nd condition
            cond2 = (y[0] < x[0] and
                     y[1] < x[1] and
                     x[0] < y[1])
 
            # If any one condition
            # is true
            if (cond1 or cond2):
                return True
 
    # If any pair of semicircles
    # doesn't exists
    return False
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 0, 15, 5, 10 ]
    N = len(arr)
 
    if (checkIntersection(arr, N)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
class pair
{
    public int first, second;
     
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
 
// Function to check if any pairs of
// the semicircles intersects or not
static bool checkIntersection(int []arr, int N)
{
 
    // Stores the coordinates of all
    // the semicircles
    List<pair > vec = new List<pair>();
 
    for(int i = 0; i < N - 1; i++)
    {
         
        // x and y are coordinates
        int x = arr[i], y = arr[i + 1];
 
        // Store the minimum and maximum
        // value of the pair
        int minn = Math.Min(x, y);
        int maxx = Math.Max(x, y);
 
        // Push the pair in vector
        vec.Add(new pair( minn, maxx ));
    }
 
    // Compare one pair with other pairs
    for(int i = 0; i < vec.Count; i++)
    {
        pair x = vec[i];
 
        // Generating the second pair
        for(int j = 0;
                j < vec.Count; j++)
        {
             
            // Extract all the second
            // pairs one by one
            pair y = vec[j];
 
            // 1st condition
            bool cond1 = (x.first < y.first &&
                         x.second < y.second &&
                          y.first < x.second);
 
            // 2nd condition
            bool cond2 = (y.first < x.first &&
                         y.second < x.second &&
                          x.first < y.second);
 
            // If any one condition
            // is true
            if (cond1 || cond2)
            {
                return true;
            }
        }
    }
 
    // If any pair of semicircles
    // doesn't exists
    return false;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 0, 15, 5, 10 };
    int N = arr.Length;
 
    if (checkIntersection(arr, N))
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program for the above approach
 
 
// Function to check if any pairs of
// the semicircles intersects or not
function checkIntersection(arr, N)
{
 
    // Stores the coordinates of all
    // the semicircles
    let vec = [];
 
    for (let i = 0; i < N - 1; i++) {
 
        // x and y are coordinates
        let x = arr[i], y = arr[i + 1];
 
        // Store the minimum and maximum
        // value of the pair
        let minn = Math.min(x, y);
        let maxx = Math.max(x, y);
 
        // Push the pair in vector
        vec.push([ minn, maxx ]);
    }
 
    // Compare one pair with other pairs
    for (let i = 0; i < vec.length; i++) {
 
        let x = vec[i];
 
        // Generating the second pair
        for (let j = 0;j < vec.length; j++) {
 
            // Extract all the second
            // pairs one by one
            let y = vec[j];
 
            // 1st condition
            let cond1 = (x[0] < y[0]
                && x[1] < y[1]
                && y[0] < x[1]);
 
            // 2nd condition
            let cond2 = (y[0] < x[0]
                && y[1] < x[1]
                && x[0] < y[1]);
 
            // If any one condition
            // is true
            if (cond1 || cond2) {
                return true;
            }
        }
    }
 
    // If any pair of semicircles
    // doesn't exists
    return false;
}
 
// Driver Code
 
let arr = [ 0, 15, 5, 10 ];
let N = arr.length;
 
if (checkIntersection(arr, N))
    document.write("Yes");
else
    document.write("No");
 
// This code is contributed by shinjanpatra.
</script>

No

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)