Horje
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 -1

Output: 
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 + c

Equating both,  

k * x = a * x2 + b * x + c
a * x2 + (b-k)*x + c = 0

Now 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();

Output

YES 2
NO
NO

Time Complexity: O(M*log N)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Counting Subarrays with elements repeated twice after swapping Counting Subarrays with elements repeated twice after swapping
Best order to maximise the value Best order to maximise the value
Min cost required to make the Array sum zero consisting of 1 and -1 Min cost required to make the Array sum zero consisting of 1 and -1
Adjacency List meaning &amp; definition in DSA Adjacency List meaning &amp; definition in DSA
Generic Tree meaning &amp; definition in DSA Generic Tree meaning &amp; definition in DSA

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje