Find line which does not intersect with parabola
Given N straight lines of form y = k * x. Also, given M parabolas of form y = a * x2 + b * x + c where a > 0. For each parabola, choose a line that does not intersect this parabola and does not touch it, the task is to find such a line for each parabola or to determine if there is no such line. Print “Yes” and the value of K for the line if the line exists for a parabola otherwise print “No”.
Note: A single line can be selected for one or more different parabolas.
Example:
Input: N = 2, M = 3,
K for N lines =
0
2
a b c for M parabolas =
2 2 1
1 -2 1
1 -2 -1Output:
YES 2
NO
NO
Approach: We can find the condition of the intersection of the parabola and line as follows:
y = k * x
y = a * x2 + b * x + cEquating both,
k * x = a * x2 + b * x + c
a * x2 + (b-k)*x + c = 0Now solution/root for this equation exists when discriminant exists. In other words, tFind line which does not intersect with parabolahe line and parabola intersect when D >= 0. So, to make this non-intersecting and non-touching, we need D < 0.
For this, we need (b-k)2 – 4*a*c < 0
=> (b-k)2 < 4*a*c —– Condition 1
=> |b-k| < √(4*a*c)
=> b – √(4*a*c) < K < b + √(4*a*c),Now we can find if any line exists that lies in this range. We can use binary search for it.
Steps that were to follow the above approach:
- Sort the values of k received for N lines
- For each parabola (a, b, c), find the index of the first smallest number among the sorted values which is greater than or equal to b.
- Check condition 1 at the value of the index
- Check condition 1 at a value at the previous index
- If the condition is satisfied in step 3 or step 4, then print “Yes” and the value
- Otherwise, print “No”
Below is the code to implement the above steps:
C++
// C++ code for the above approach. #include <bits/stdc++.h> using namespace std; struct Parabola { int a, b, c; }; // Function to print the required // line for each parabola. void findLine( int lines[], Parabola parabolas[], int n, int m) { sort(lines, lines + n); for ( int i = 0; i < m; i++) { int a, b, c; a = parabolas[i].a; b = parabolas[i].b; c = parabolas[i].c; int ind = lower_bound(lines, lines + n, b) - lines; if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) { cout << "YES " << lines[ind] << "\n" ; continue ; } if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) { cout << "YES " << lines[ind - 1] << "\n" ; continue ; } cout << "NO\n" ; } } // Driver's code int main() { int n = 2, m = 3; int lines[] = { 0, 2 }; Parabola parabolas[] = { { 2, 2, 1 }, { 1, -2, 1 }, { 1, -2, -1 } }; // Function Call findLine(lines, parabolas, n, m); return 0; } |
Java
//Java Implementation import java.util.Arrays; class Parabola { int a, b, c; } public class GFG { public static void findLine( int [] lines, Parabola[] parabolas, int n, int m) { Arrays.sort(lines); for ( int i = 0 ; i < m; i++) { int a = parabolas[i].a; int b = parabolas[i].b; int c = parabolas[i].c; int ind = Arrays.binarySearch(lines, b); if (ind >= 0 ) { if ((lines[ind] - b) * (lines[ind] - b) < 4 * a * c) { System.out.println( "YES " + lines[ind]); continue ; } } ind = -ind - 1 ; if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) { System.out.println( "YES " + lines[ind]); } else if (ind > 0 && (lines[ind - 1 ] - b) * (lines[ind - 1 ] - b) < 4 * a * c) { System.out.println( "YES " + lines[ind - 1 ]); } else { System.out.println( "NO" ); } } } public static void main(String[] args) { int n = 2 , m = 3 ; int [] lines = { 0 , 2 }; Parabola[] parabolas = { new Parabola(), new Parabola(), new Parabola() }; parabolas[ 0 ].a = 2 ; parabolas[ 0 ].b = 2 ; parabolas[ 0 ].c = 1 ; parabolas[ 1 ].a = 1 ; parabolas[ 1 ].b = - 2 ; parabolas[ 1 ].c = 1 ; parabolas[ 2 ].a = 1 ; parabolas[ 2 ].b = - 2 ; parabolas[ 2 ].c = - 1 ; // Function Call findLine(lines, parabolas, n, m); } } //This code is contributed by Aditi Tyagi |
Python3
import bisect class Parabola: def __init__( self , a, b, c): self .a = a self .b = b self .c = c # Function to print the required # line for each parabola. def findLine(lines, parabolas, n, m): lines.sort() for i in range (m): a = parabolas[i].a b = parabolas[i].b c = parabolas[i].c ind = bisect.bisect_left(lines, b) if ind < n and (lines[ind] - b) * (lines[ind] - b) < 4 * a * c: print ( "YES" , lines[ind]) continue if ind > 0 and (lines[ind - 1 ] - b) * (lines[ind - 1 ] - b) < 4 * a * c: print ( "YES" , lines[ind - 1 ]) continue print ( "NO" ) # Driver's code if __name__ = = '__main__' : n = 2 m = 3 lines = [ 0 , 2 ] parabolas = [Parabola( 2 , 2 , 1 ), Parabola( 1 , - 2 , 1 ), Parabola( 1 , - 2 , - 1 )] # Function Call findLine(lines, parabolas, n, m) |
C#
using System; public class Parabola { public int a, b, c; } public class Program { // Function to print the required // line for each parabola. public static void FindLine( int [] lines, Parabola[] parabolas, int n, int m) { Array.Sort(lines); for ( int i = 0; i < m; i++) { int a, b, c; a = parabolas[i].a; b = parabolas[i].b; c = parabolas[i].c; int ind = Array.BinarySearch(lines, b); ind = ind >= 0 ? ind : ~ind; if (ind < n && (lines[ind] - b) * (lines[ind] - b) < 4 * a * c) { Console.WriteLine( "YES " + lines[ind]); continue ; } if (ind > 0 && (lines[ind - 1] - b) * (lines[ind - 1] - b) < 4 * a * c) { Console.WriteLine( "YES " + lines[ind - 1]); continue ; } Console.WriteLine( "NO" ); } } // Driver's code public static void Main() { int n = 2, m = 3; int [] lines = { 0, 2 }; Parabola[] parabolas = { new Parabola {a = 2, b = 2, c = 1}, new Parabola {a = 1, b = -2, c = 1}, new Parabola {a = 1, b = -2, c = -1} }; // Function Call FindLine(lines, parabolas, n, m); } } |
Javascript
// JavaScript code for the above approach. class parabola { constructor(a, b, c) { this .a = a; this .b = b; this .c = c; } } // Function to print the required line // for each parabola. function findLine(lines, parabolas, n, m) { // Sort the lines array in ascending order lines.sort((a, b) => a - b); // Loop through each parabola for (let i = 0; i < m; i++) { let a = parabolas[i].a; let b = parabolas[i].b; let c = parabolas[i].c; // Use binary search to find the index of the // closest line to 'b' let ind = binarySearch(lines, b); if ( ind < n && Math.pow(lines[ind] - b, 2) < 4 * a * c ) { console.log( "YES " + lines[ind]); } else if ( ind > 0 && Math.pow(lines[ind - 1] - b, 2) < 4 * a * c ) { console.log( "YES " + lines[ind - 1]); } else { console.log( "NO" ); } } } // Binary Search function to find the // index of the closest value to 'target' function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } // Driver's code function main() { let n = 2; let m = 3; let lines = [0, 2]; let parabolas = [ new parabola(2, 2, 1), new parabola(1, -2, 1), new parabola(1, -2, -1), ]; // Function Call findLine(lines, parabolas, n, m); } main(); |
YES 2 NO NO
Time Complexity: O(M*log N)
Auxiliary Space: O(1)