Dada una array arr que contiene N puntos de coordenadas en un plano, la tarea es verificar si los puntos de coordenadas se encuentran en una línea recta o no. Si se encuentran en una línea recta, imprima Sí y también la ecuación de esa línea, de lo contrario, imprima No.
Ejemplo:
Entrada: arr[] = {{1, 1}, {2, 2}, {3, 3}}
Salida:
Sí
1x- 1y=0Entrada: arr[] = {{0, 1}, {2, 0}}
Salida:
Sí
2y+x-2 = 0Entrada: arr[] = {{1, 5}, {2, 2}, {4, 6}, {3, 5}}
Salida: No
Enfoque: la idea es encontrar la ecuación de la línea que se puede formar usando cualquier par de puntos dados en la array y si todos los demás puntos satisfacen la ecuación de la línea formada usando el par de puntos, entonces todos estos puntos juntos formar una línea recta. Entonces, si todos los puntos satisfacen la ecuación de la línea, imprima Sí seguido de la ecuación de la línea; de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if a straight line
// can be formed using N points
void isStraightLinePossibleEq(
vector<pair<int, int> > arr,
int n)
{
// First pair of point (x0, y0)
int x0 = arr[0].first;
int y0 = arr[0].second;
// Second pair of point (x1, y1)
int x1 = arr[1].first;
int y1 = arr[1].second;
int dx = x1 - x0,
dy = y1 - y0,
c = dy * x0 - dx * y0;
// Loop to iterate over the points
// and check whether they satisfy
// the equation or not.
for (int i = 2; i < n; i++) {
int x = arr[i].first, y = arr[i].second;
if ((dx * y) - (dy * x) != c) {
cout << "No";
return;
}
}
cout << "Yes" << endl;
cout << dy << "x-" << dx
<< "y=" << c << "\n";
}
// Driver Code
int main()
{
// Array of points
vector<pair<int, int> > arr
= { { 0, 0 }, { 1, 1 }, { 3, 3 }, { 2, 2 } };
int N = 2;
// Function Call
isStraightLinePossibleEq(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to check if a straight line
// can be formed using N points
static void isStraightLinePossibleEq(int arr[][], int n)
{
// First pair of point (x0, y0)
int x0 = arr[0][0];
int y0 = arr[0][1];
// Second pair of point (x1, y1)
int x1 = arr[1][0];
int y1 = arr[1][1];
int dx = x1 - x0,
dy = y1 - y0,
c = dy * x0 - dx * y0;
// Loop to iterate over the points
// and check whether they satisfy
// the equation or not.
for (int i = 2; i < n; i++) {
int x = arr[i][0], y = arr[i][1];
if ((dx * y) - (dy * x) != c) {
System.out.print("No");
return;
}
}
System.out.print("Yes" + "\n");
System.out.print(dy + "x-" + dx
+ "y=" + c + "\n");
}
// Driver Code
public static void main(String args[])
{
// Array of points
int arr[][] = {{ 0, 0 }, { 1, 1 }, { 3, 3 }, { 2, 2 }};
int N = 2;
// Function Call
isStraightLinePossibleEq(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python code for the above approach
# Function to check if a straight line
# can be formed using N points
def isStraightLinePossibleEq(arr, n):
# First pair of point (x0, y0)
x0 = arr[0][0]
y0 = arr[0][1]
# Second pair of point (x1, y1)
x1 = arr[1][0]
y1 = arr[1][1]
dx = x1 - x0
dy = y1 - y0
c = dy * x0 - dx * y0
# Loop to iterate over the points
# and check whether they satisfy
# the equation or not.
for i in range(2, n):
x = arr[i][0], y = arr[i][1]
if (dx * y) - (dy * x) != c:
print("No")
return
print("Yes")
print(str(dy)+ "x" +"-" + str(dx)+ "y"+ "="+ str(c))
# Driver Code
# Array of points
arr = [[0, 0], [1, 1], [3, 3], [2, 2]]
N = 2
# Function Call
isStraightLinePossibleEq(arr, N)
# This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to check if a straight line
// can be formed using N points
static void isStraightLinePossibleEq(int [,]arr, int n)
{
// First pair of point (x0, y0)
int x0 = arr[0, 0];
int y0 = arr[0, 1];
// Second pair of point (x1, y1)
int x1 = arr[1, 0];
int y1 = arr[1, 1];
int dx = x1 - x0,
dy = y1 - y0,
c = dy * x0 - dx * y0;
// Loop to iterate over the points
// and check whether they satisfy
// the equation or not.
for (int i = 2; i < n; i++) {
int x = arr[i, 0], y = arr[i, 1];
if ((dx * y) - (dy * x) != c) {
Console.Write("No");
return;
}
}
Console.Write("Yes" + "\n");
Console.Write(dy + "x-" + dx
+ "y=" + c + "\n");
}
// Driver Code
public static void Main()
{
// Array of points
int[,] arr = new int[4, 2] {{ 0, 0 }, { 1, 1 }, { 3, 3 }, { 2, 2 }};
int N = 2;
// Function Call
isStraightLinePossibleEq(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to check if a straight line
// can be formed using N points
const isStraightLinePossibleEq = (arr, n) => {
// First pair of point (x0, y0)
let x0 = arr[0][0];
let y0 = arr[0][1];
// Second pair of point (x1, y1)
let x1 = arr[1][0];
let y1 = arr[1][1];
let dx = x1 - x0,
dy = y1 - y0,
c = dy * x0 - dx * y0;
// Loop to iterate over the points
// and check whether they satisfy
// the equation or not.
for (let i = 2; i < n; i++) {
let x = arr[i][0], y = arr[i][1];
if ((dx * y) - (dy * x) != c) {
cout << "No";
return;
}
}
document.write("Yes<br/>");
document.write(`${dy}x-${dx}y=${c}<br/>`);
}
// Driver Code
// Array of points
let arr = [[0, 0], [1, 1], [3, 3], [2, 2]];
let N = 2;
// Function Call
isStraightLinePossibleEq(arr, N);
// This code is contributed by rakeshsahni
</script>
Producción
Yes 1x-1y=0
Complejidad temporal: O(N)
Espacio auxiliar: O(1)