Given an array arr[] consisting of N integers such that each pair of points (x, y) represents the endpoints of the semicircle as (x, 0) and (y, 0), the task is to check if any pair of semicircles intersect or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {0, 15, 5, 10}
Output: NoInput: arr[] = {0, 10, 5, 15}
Output: Yes
Approach: The given problem can be solved by checking if any pairs of semicircles intersect or not and then print the elements accordingly. Follow the steps below to solve the problem:
- Store all the possible semicircles in a vector with their corresponding x coordinates and y coordinates.
- Now, generate all possible pairs of the above vectors and perform the following steps:
- Let the pair of coordinates be X and Y and check if the circles intersect or not using the following conditions:
- If the value of (X[0] < Y[0], X[1] < Y[1] and Y[0] < X[2]) or (Y[0] < X[0], Y[1] < X[1], and X[0] < Y[1]), then the semicircle intersects. Otherwise, it doesn’t intersect.
- If the above two circles intersect, then print “Yes” and break out of the loop.
- Let the pair of coordinates be X and Y and check if the circles intersect or not using the following conditions:
- After completing the above steps, if any pair of circles doesn’t intersect, then print “No”.
C++
// C++ program for the above approach#include <iostream>#include <vector>using namespace std;// Function to check if any pairs of// the semicircles intersects or notbool 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 Codeint 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
// Java program for the above approachimport 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 notstatic 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 Codepublic 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
# Python3 program for the above approach# Function to check if any pairs of# the semicircles intersects or notdef 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 Codeif __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#
// C# program for the above approachusing 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 notstatic 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 Codepublic 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 |
Javascript
<script>// JavaScript program for the above approach// Function to check if any pairs of// the semicircles intersects or notfunction 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 Codelet 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> |
Output:
No
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
