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