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