Líneas mínimas para cubrir todos los puntos

Dados N puntos en un espacio bidimensional, necesitamos imprimir el conteo del número mínimo de líneas que atraviesan todos estos N puntos y que también pasan por un punto específico (xO, yO).
Ejemplos: 
 

If given points are (-1, 3), (4, 3), (2, 1), (-1, -2), 
(3, -3) and (xO, yO) point is (1, 0) i.e. every line
must go through this point. 
Then we have to draw at least two lines to cover all
these points going through (xO, yO) as shown in below
diagram.

Podemos resolver este problema considerando la pendiente de todos los puntos con (xO, yO). Si dos puntos distintos tienen la misma pendiente con (xO, yO), entonces se pueden cubrir con la misma línea solo para que podamos rastrear la pendiente de cada punto y cada vez que obtengamos una nueva pendiente, aumentaremos nuestro recuento de líneas en uno. 
En el siguiente código, la pendiente se almacena como un par de enteros para eliminar el problema de precisión y se utiliza un conjunto para realizar un seguimiento de las pendientes que se producen. 
Consulte el código a continuación para una mejor comprensión. 
 

// C++ program to get minimum lines to cover
// all the points
#include <bits/stdc++.h>
using namespace std;
 
//    Utility method to get gcd of a and b
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
 
//    method returns reduced form of dy/dx as a pair
pair<int, int> getReducedForm(int dy, int dx)
{
    int g = gcd(abs(dy), abs(dx));
 
    //    get sign of result
    bool sign = (dy < 0) ^ (dx < 0);
 
    if (sign)
        return make_pair(-abs(dy) / g, abs(dx) / g);
    else
        return make_pair(abs(dy) / g, abs(dx) / g);
}
 
/*    method returns minimum number of lines to
    cover all points where all lines goes
    through (xO, yO) */
int minLinesToCoverPoints(int points[][2], int N,
                                   int xO, int yO)
{
    //    set to store slope as a pair
    set< pair<int, int> > st;
    pair<int, int> temp;
    int minLines = 0;
 
    //    loop over all points once
    for (int i = 0; i < N; i++)
    {
        //    get x and y co-ordinate of current point
        int curX = points[i][0];
        int curY = points[i][1];
 
        temp = getReducedForm(curY - yO, curX - xO);
 
        // if this slope is not there in set,
        // increase ans by 1 and insert in set
        if (st.find(temp) == st.end())
        {
            st.insert(temp);
            minLines++;
        }
    }
 
    return minLines;
}
 
// Driver code to test above methods
int main()
{
    int xO, yO;
    xO = 1;
    yO = 0;
 
    int points[][2] =
    {
        {-1, 3},
        {4, 3},
        {2, 1},
        {-1, -2},
        {3, -3}
    };
 
    int N = sizeof(points) / sizeof(points[0]);
    cout << minLinesToCoverPoints(points, N, xO, yO);
    return 0;
}

// Java Program for above approach
import java.io.*;
import java.util.*;
import java.util.Set;
 
// User defined Pair class
class Pair {
    int x;
    int y;
 
    // Constructor
    public Pair(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
class GFG {
    //  Utility method to get gcd of a and b
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    // method returns reduced form of dy/dx as a pair
    public static Pair getReducedForm(int dy, int dx)
    {
        int g = gcd(Math.abs(dy), Math.abs(dx));
 
        //    get sign of result
        boolean sign = (dy < 0) ^ (dx < 0);
        Pair res = new Pair(0, 0);
 
        if (sign) {
            res.x = -Math.abs(dy) / g;
            res.y = Math.abs(dx) / g;
        }
        else {
            res.x = Math.abs(dy) / g;
            res.y = Math.abs(dx) / g;
        }
        return res;
    }
 
    /*  method returns minimum number of lines to
    cover all points where all lines goes
    through (xO, yO) */
 
    public static int minLinesToCoverPoints(int points[][],
                                            int N, int xO,
                                            int yO)
    {
        // set to store slope as a string
        Set<String> st = new HashSet<String>();
 
        Pair temp;
        int minLines = 0;
 
        //    loop over all points once
        for (int i = 0; i < N; i++) {
            //    get x and y co-ordinate of current point
            int curX = points[i][0];
            int curY = points[i][1];
 
            temp = getReducedForm(curY - yO, curX - xO);
 
            // convert pair into string to store in set
            String tempString = temp.x + "," + temp.y;
 
            // if this slope is not there in set,
            // increase ans by 1 and insert in set
 
            if (st.contains(tempString) == false) {
                st.add(tempString);
                minLines += 1;
            }
        }
 
        return minLines;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int xO, yO;
        xO = 1;
        yO = 0;
 
        int points[][] = { { -1, 3 },
                           { 4, 3 },
                           { 2, 1 },
                           { -1, -2 },
                           { 3, -3 } };
 
        int N = points.length;
        System.out.println(
            minLinesToCoverPoints(points, N, xO, yO));
    }
}
 
// This code is contributed by rj13to.

# Python3 program to get minimum lines to cover
# all the points
 
# Utility method to get gcd of a and b
def gcd(a, b):
    if (b == 0):
        return a
    return gcd(b, a % b)
 
# method returns reduced form of dy/dx as a pair
def getReducedForm(dy, dx):
    g = gcd(abs(dy), abs(dx))
 
    # get sign of result
    sign = (dy < 0) ^ (dx < 0)
 
    if (sign):
        return (-abs(dy) // g, abs(dx) // g)
    else:
        return (abs(dy) // g, abs(dx) // g)
 
# /* method returns minimum number of lines to
#     cover all points where all lines goes
#     through (xO, yO) */
def minLinesToCoverPoints(points, N, xO, yO):
     
    # set to store slope as a pair
    st = dict()
    minLines = 0
 
    # loop over all points once
    for i in range(N):
         
        # get x and y co-ordinate of current point
        curX = points[i][0]
        curY = points[i][1]
 
        temp = getReducedForm(curY - yO, curX - xO)
 
        # if this slope is not there in set,
        # increase ans by 1 and insert in set
        if (temp not in st):
            st[temp] = 1
            minLines += 1
 
    return minLines
 
# Driver code
xO = 1
yO = 0
 
points =[[-1, 3],
         [4, 3],
         [2, 1],
         [-1, -2],
         [3, -3]]
 
N = len(points)
print(minLinesToCoverPoints(points, N, xO, yO))
 
# This code is contributed by mohit kumar 29

// C# program to print the count of the minimum number
// of lines which traverse through all these N points
// and which go through a specific (xO, yO) point also
using System;
using System.Collections.Generic;
using System.Linq;
 
// User defined Pair class
public class Pair {
  public int x;
  public int y;
 
  // Constructor
  public Pair(int x, int y)
  {
    this.x = x;
    this.y = y;
  }
}
 
public class GFG{
 
  //  Utility method to get gcd of a and b
  public static int gcd(int a, int b)
  {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }
   
  // method returns reduced form of dy/dx as a pair
  public static Pair getReducedForm(int dy, int dx)
  {
    int g = gcd(Math.Abs(dy), Math.Abs(dx));
 
    //    get sign of result
    bool sign = (dy < 0) ^ (dx < 0);
    Pair res = new Pair(0, 0);
 
    if (sign) {
      res.x = -Math.Abs(dy) / g;
      res.y = Math.Abs(dx) / g;
    }
    else {
      res.x = Math.Abs(dy) / g;
      res.y = Math.Abs(dx) / g;
    }
    return res;
  }
 
  /*  method returns minimum number of lines to
    cover all points where all lines goes
    through (xO, yO) */
  static public int minLinesToCoverPoints(int[,] points, int N, int xO, int yO){
    // set to store slope as a string
    HashSet<string> st = new HashSet<string>();
 
    Pair temp;
    int minLines = 0;
 
    //    loop over all points once
    for (int i = 0; i < N; i++) {
      //    get x and y co-ordinate of current point
      int curX = points[i,0];
      int curY = points[i,1];
 
      temp = getReducedForm(curY - yO, curX - xO);
 
      // convert pair into string to store in set
      String tempString = temp.x + "," + temp.y;
 
      // if this slope is not there in set,
      // increase ans by 1 and insert in set
 
      if (st.Contains(tempString) == false) {
        st.Add(tempString);
        minLines += 1;
      }
    }
 
    return minLines;
 
  }
 
  //Driver Code
  static public void Main (){
    int xO, yO;
    xO = 1;
    yO = 0;
 
    int[,] points = new int[,] { { -1, 3 },
                                { 4, 3 },
                                { 2, 1 },
                                { -1, -2 },
                                { 3, -3 } };
 
    int N = points.GetLength(0);
    Console.Write(minLinesToCoverPoints(points, N, xO, yO));
  }
}
 
// This code is contributed by shruti456rawal

<script>
// Javascript program to get minimum lines to cover
// all the points
 
    //    Utility method to get gcd of a and b
    function gcd(a,b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
     
    // method returns reduced form of dy/dx as a pair
    function getReducedForm(dy,dx)
    {
        let g = gcd(Math.abs(dy), Math.abs(dx));
   
    // get sign of result
    let sign = (dy < 0) ^ (dx < 0);
       
    if (sign)
    {  
        return [Math.floor(-Math.abs(dy) / g), Math.floor(Math.abs(dx) / g)];
             
    }
    else
        return [Math.floor(Math.abs(dy) / g), Math.floor(Math.abs(dx) / g)];
    }
     
    /*    method returns minimum number of lines to
    cover all points where all lines goes
    through (xO, yO) */
    function minLinesToCoverPoints(points,N,x0,y0)
    {
        let st=new Set();
        let temp;
        let minLines = 0;
         
        // loop over all points once
    for (let i = 0; i < N; i++)
    {
        // get x and y co-ordinate of current point
        let curX = points[i][0];
        let curY = points[i][1];
   
        temp = getReducedForm(curY - yO, curX - xO);
           
        // if this slope is not there in set,
        // increase ans by 1 and insert in set
        if (!st.has(temp.join("")))
        {
             
            st.add(temp.join(""));
            minLines++;
        }
    }
   
    return minLines;
    }
     
    // Driver code to test above methods
    let xO, yO;
    xO = 1;
    yO = 0;
     
    let points =[[-1, 3],
         [4, 3],
         [2, 1],
         [-1, -2],
         [3, -3]];
    let N = points.length;
    document.write(minLinesToCoverPoints(points, N, xO, yO))
    
// This code is contributed by unknown2108
</script>

Producción: 
 

2

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)

Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.