Given a matrix lines[][] of size N * 3, such that ith row denotes a line having the equation lines[i][0] * x + lines[i][1]*y = lines[i][2], and integers X and Y, denoting coordinates of a point (X, Y), the task is to count the number of lines from the given matrix which intersect with one another at the given point (X, Y).
Examples:
Input: N=5, X = 3, Y = 4, Lines[][] = {{4, -1, 8}, {2, -7, -2}, {1, 1, 7}, {1, -3, 5}, {1, 0, 3}}
Output: 3
Explanation:
Lines 4*x – y = 8, 1*x + 1* y = 7 and 1*x – 0*y = 3 intersect with each other at point (3, 4).Input: N=4, X = -2, Y = 3, Lines[][] = {{3, -2, -12}, {1, 3, 5}, {1, -1, -5}, {2, 3, 4}}
Output: 2
Explanation:
Lines 3*x – 2*y = -12 and 1*x – 1*y = -5 intersect with each other at point (-2, 3).
Naive Approach: The simplest approach to solve the problem is that for each line, find its intersection point with other lines and check if they intersect at the given point (X, Y) or not. Finally, print the count of lines intersecting at (X, Y).
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using the observation:
If two lines pass through the same point, then they will definitely intersect at that point.
Follow the steps below to solve the problems:
- So, count the number of lines passing through the given point, let the count of lines be cnt.
- After calculating the above step, print the total number of intersections:
Count of intersections of cnt lines intersecting at (X, Y) = cntC2
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Structure to store point struct Point { int x, y; }; // Structure to store line struct Line { int a, b, c; }; // Function to check if a line // passes through a point or not bool point_lies_on_line(Line l, Point p) { // Condition for the line // to pass through point p if (l.a * p.x + l.b * p.y == l.c) { return true ; } return false ; } // Function to find lines // intersecting at a given point int intersecting_at_point( vector<Line>& lines, Point p) { int cnt = 0; for ( int i = 0; i < lines.size(); i++) { // If the point lies on a line if (point_lies_on_line(lines[i], p)) { // Increment cnt cnt++; } } // Count of intersections int ans = (cnt * (cnt - 1)) / 2; // Return answer return ans; } // Driver Code int main() { // Number of lines int N = 5; // Point (x, y) Point p = { 3, 4 }; // Array to store the lines vector<Line> lines; lines.push_back({ 4, -1, 8 }); lines.push_back({ 1, 0, 3 }); lines.push_back({ 1, 1, 7 }); lines.push_back({ 2, -7, -2 }); lines.push_back({ 1, -3, 5 }); // Function call int ans = intersecting_at_point(lines, p); cout << ans << endl; return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Structure to store point static class Point { int x, y; public Point( int x, int y) { super (); this .x = x; this .y = y; } }; // Structure to store line static class Line { int a, b, c; public Line( int a, int b, int c) { super (); this .a = a; this .b = b; this .c = c; } }; // Function to check if a line // passes through a point or not static boolean point_lies_on_line(Line l, Point p) { // Condition for the line // to pass through point p if (l.a * p.x + l.b * p.y == l.c) { return true ; } return false ; } // Function to find lines // intersecting at a given point static int intersecting_at_point(Vector<Line> lines, Point p) { int cnt = 0 ; for ( int i = 0 ; i < lines.size(); i++) { // If the point lies on a line if (point_lies_on_line(lines.get(i), p)) { // Increment cnt cnt++; } } // Count of intersections int ans = (cnt * (cnt - 1 )) / 2 ; // Return answer return ans; } // Driver Code public static void main(String[] args) { // Number of lines int N = 5 ; // Point (x, y) Point p = new Point( 3 , 4 ); // Array to store the lines Vector<Line> lines = new Vector<Line>(); lines.add( new Line( 4 , - 1 , 8 )); lines.add( new Line( 1 , 0 , 3 )); lines.add( new Line( 1 , 1 , 7 )); lines.add( new Line( 2 , - 7 , - 2 )); lines.add( new Line( 1 , - 3 , 5 )); // Function call int ans = intersecting_at_point(lines, p); System.out.print(ans + "\n" ); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement # the above approach # Function to check if a line # passes through a poor not def point_lies_on_line(l, p): # Condition for the line # to pass through pop if (l[ 0 ] * p[ 0 ] + l[ 1 ] * p[ 1 ] = = l[ 2 ]): return True return False # Function to find lines # intersecting at a given point def intersecting_at_point(lines, p): cnt = 0 for i in range ( len (lines)): # If the polies on a line if (point_lies_on_line(lines[i], p)): # Increment cnt cnt + = 1 # Count of intersections ans = (cnt * (cnt - 1 )) / / 2 # Return answer return ans # Driver Code if __name__ = = '__main__' : # Number of lines N = 5 # Po(x, y) p = [ 3 , 4 ] # Array to store the lines lines = [] lines.append([ 4 , - 1 , 8 ]) lines.append([ 1 , 0 , 3 ]) lines.append([ 1 , 1 , 7 ]) lines.append([ 2 , - 7 , - 2 ]) lines.append([ 1 , - 3 , 5 ]) # Function call ans = intersecting_at_point(lines, p) print (ans) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Structure to store point class Point { public int x, y; public Point( int x, int y) { this .x = x; this .y = y; } }; // Structure to store line class Line { public int a, b, c; public Line( int a, int b, int c) { this .a = a; this .b = b; this .c = c; } }; // Function to check if a line // passes through a point or not static bool point_lies_on_line(Line l, Point p) { // Condition for the line // to pass through point p if (l.a * p.x + l.b * p.y == l.c) { return true ; } return false ; } // Function to find lines // intersecting at a given point static int intersecting_at_point(List<Line> lines, Point p) { int cnt = 0; for ( int i = 0; i < lines.Count; i++) { // If the point lies on a line if (point_lies_on_line(lines[i], p)) { // Increment cnt cnt++; } } // Count of intersections int ans = (cnt * (cnt - 1)) / 2; // Return answer return ans; } // Driver Code public static void Main(String[] args) { // Number of lines int N = 5; // Point (x, y) Point p = new Point(3, 4); // Array to store the lines List<Line> lines = new List<Line>(); lines.Add( new Line(4, -1, 8)); lines.Add( new Line(1, 0, 3)); lines.Add( new Line(1, 1, 7)); lines.Add( new Line(2, -7, -2)); lines.Add( new Line(1, -3, 5)); // Function call int ans = intersecting_at_point(lines, p); Console.Write(ans + "\n" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to check if a line // passes through a point or not function point_lies_on_line(l, p) { // Condition for the line // to pass through point p if (l[0] * p[0] + l[1] * p[1] == l[2]) { return true ; } return false ; } // Function to find lines // intersecting at a given point function intersecting_at_point( lines, p) { var cnt = 0; for ( var i = 0; i < lines.length; i++) { // If the point lies on a line if (point_lies_on_line(lines[i], p)) { // Increment cnt cnt++; } } // Count of intersections var ans = (cnt * (cnt - 1)) / 2; // Return answer return ans; } // Driver Code // Number of lines var N = 5; // Point (x, y) var p = [3, 4]; // Array to store the lines var lines = []; lines.push([ 4, -1, 8 ]); lines.push([ 1, 0, 3 ]); lines.push([ 1, 1, 7 ]); lines.push([ 2, -7, -2 ]); lines.push([ 1, -3, 5 ]); // Function call var ans = intersecting_at_point(lines, p); document.write( ans ); </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!