Dada una array líneas[][] de tamaño N * 3 , tal que la i -ésima fila denota una línea que tiene la ecuación líneas[i][0] * x + líneas[i][1]*y = líneas[i][ 2] y los números enteros X e Y , que denotan las coordenadas de un punto (X, Y) , la tarea es contar el número de líneas de la array dada que se cruzan entre sí en el punto dado (X, Y) .
Ejemplos:
Entrada: N=5, X = 3, Y = 4, Líneas[][] = {{4, -1, 8}, {2, -7, -2}, {1, 1, 7}, {1 , -3, 5}, {1, 0, 3}}
Salida: 3
Explicación: Las
líneas 4*x – y = 8, 1*x + 1* y = 7 y 1*x – 0*y = 3 se cruzan con entre sí en el punto (3, 4).Entrada: N=4, X = -2, Y = 3, Líneas[][] = {{3, -2, -12}, {1, 3, 5}, {1, -1, -5}, {2, 3, 4}}
Salida: 2
Explicación: Las
líneas 3*x – 2*y = -12 y 1*x – 1*y = -5 se cruzan entre sí en el punto (-2, 3).
Enfoque ingenuo: el enfoque más simple para resolver el problema es que para cada línea, encuentre su punto de intersección con otras líneas y verifique si se cruzan en el punto dado (X, Y) o no. Finalmente, imprima el conteo de líneas que se cruzan en (X, Y).
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la observación:
Si dos rectas pasan por el mismo punto, definitivamente se intersecarán en ese punto.
Siga los pasos a continuación para resolver los problemas:
- Entonces, cuente el número de líneas que pasan por el punto dado, sea cnt el número de líneas .
- Después de calcular el paso anterior, imprima el número total de intersecciones:
Recuento de intersecciones de líneas de cnt que se cruzan en (X, Y) = cnt C 2
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sri_srajit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA