Cuente el máximo de puntos en la misma línea

Dado N punto en un plano 2D como un par de coordenadas (x, y), necesitamos encontrar el número máximo de puntos que se encuentran en la misma línea.

Ejemplos: 

Input : points[] = {-1, 1}, {0, 0}, {1, 1}, 
                    {2, 2}, {3, 3}, {3, 4} 
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}

Podemos resolver el problema anterior siguiendo el siguiente enfoque: para cada punto p, calcule su pendiente con otros puntos y use un mapa para registrar cuántos puntos tienen la misma pendiente, por lo que podemos averiguar cuántos puntos están en la misma línea con p como su un punto. Para cada punto, siga haciendo lo mismo y actualice el número máximo de puntos encontrados hasta el momento.

Algunas cosas a tener en cuenta en la implementación son: 

1. si dos puntos son (x1, y1) y (x2, y2) entonces su pendiente será (y2 – y1) / (x2 – x1) que puede ser un valor doble y puede causar problemas de precisión. Para deshacernos de los problemas de precisión, tratamos la pendiente como un par ((y2 – y1), (x2 – x1)) en lugar de una relación y reducimos el par por su gcd antes de insertarlo en el mapa. A continuación, los puntos de código que son verticales o repetidos se tratan por separado.
2. Si usamos unordered_map en C++ o HashMap en Java para almacenar el par de pendientes, la complejidad temporal total de la solución será O(n^2) y la complejidad espacial será O(n).

Implementación:

/* C/C++ program to find maximum number of point
which lie on same line */
#include <bits/stdc++.h>
#include <boost/functional/hash.hpp>
 
using namespace std;
 
// method to find maximum collinear point
int maxPointOnSameLine(vector< pair<int, int> > points)
{
    int N = points.size();
    if (N < 2)
        return N;
 
    int maxPoint = 0;
    int curMax, overlapPoints, verticalPoints;
 
    // here since we are using unordered_map
    // which is based on hash function
    //But by default we don't have hash function for pairs
    //so we'll use hash function defined in Boost library
    unordered_map<pair<int, int>, int,boost::
              hash<pair<int, int> > > slopeMap;
 
    // looping for each point
    for (int i = 0; i < N; i++)
    {
        curMax = overlapPoints = verticalPoints = 0;
 
        // looping from i + 1 to ignore same pair again
        for (int j = i + 1; j < N; j++)
        {
            // If both point are equal then just
            // increase overlapPoint count
            if (points[i] == points[j])
                overlapPoints++;
 
            // If x co-ordinate is same, then both
            // point are vertical to each other
            else if (points[i].first == points[j].first)
                verticalPoints++;
 
            else
            {
                int yDif = points[j].second - points[i].second;
                int xDif = points[j].first - points[i].first;
                int g = __gcd(xDif, yDif);
 
                // reducing the difference by their gcd
                yDif /= g;
                xDif /= g;
 
                // increasing the frequency of current slope
                // in map
                slopeMap[make_pair(yDif, xDif)]++;
                curMax = max(curMax, slopeMap[make_pair(yDif, xDif)]);
            }
 
            curMax = max(curMax, verticalPoints);
        }
 
        // updating global maximum by current point's maximum
        maxPoint = max(maxPoint, curMax + overlapPoints + 1);
 
        // printf("maximum collinear point
        // which contains current point
        // are : %d\n", curMax + overlapPoints + 1);
        slopeMap.clear();
    }
 
    return maxPoint;
}
 
// Driver code
int main()
{
    const int N = 6;
    int arr[N][2] = {{-1, 1}, {0, 0}, {1, 1}, {2, 2},
                    {3, 3}, {3, 4}};
 
    vector< pair<int, int> > points;
    for (int i = 0; i < N; i++)
        points.push_back(make_pair(arr[i][0], arr[i][1]));
 
    cout << maxPointOnSameLine(points) << endl;
 
    return 0;
}

# python3 program to find maximum number of 2D points that lie on the same line.
 
from collections import defaultdict
from math import gcd
from typing import DefaultDict, List, Tuple
 
IntPair = Tuple[int, int]
 
 
def normalized_slope(a: IntPair, b: IntPair) -> IntPair:
    """
    Returns normalized (rise, run) tuple. We won't return the actual rise/run
    result in order to avoid floating point math, which leads to faulty
    comparisons.
 
    See
    https://en.wikipedia.org/wiki/Floating-point_arithmetic#Accuracy_problems
    """
    run = b[0] - a[0]
 
    # normalize undefined slopes to (1, 0)
    if run == 0:
        return (1, 0)
 
    # normalize to left-to-right
    if run < 0:
        a, b = b, a
        run = b[0] - a[0]
 
    rise = b[1] - a[1]
    # Normalize by greatest common divisor.
    # math.gcd only works on positive numbers.
    gcd_ = gcd(abs(rise), run)
    return (
        rise // gcd_,
        run // gcd_,
    )
 
 
def maximum_points_on_same_line(points: List[List[int]]) -> int:
    # You need at least 3 points to potentially have non-collinear points.
    # For [0, 2] points, all points are on the same line.
    if len(points) < 3:
        return len(points)
 
    # Note that every line we find will have at least 2 points.
    # There will be at least one line because len(points) >= 3.
    # Therefore, it's safe to initialize to 0.
    max_val = 0
 
    for a_index in range(0, len(points) - 1):
        # All lines in this iteration go through point a.
        # Note that lines a-b and a-c cannot be parallel.
        # Therefore, if lines a-b and a-c have the same slope, they're the same
        # line.
        a = tuple(points[a_index])
        # Fresh lines already have a, so default=1
        slope_counts: DefaultDict[IntPair, int] = defaultdict(lambda: 1)
 
        for b_index in range(a_index + 1, len(points)):
            b = tuple(points[b_index])
            slope_counts[normalized_slope(a, b)] += 1
 
        max_val = max(
            max_val,
            max(slope_counts.values()),
        )
 
    return max_val
 
 
print(maximum_points_on_same_line([
    [-1, 1],
    [0, 0],
    [1, 1],
    [2, 2],
    [3, 3],
    [3, 4],
]))
 
# This code is contributed by Jose Alvarado Torre

/* JavaScript program to find maximum number of point
which lie on same line */
 
// Function to find gcd of two numbers
let gcd = function(a, b) {
  if (!b) {
    return a;
  }
  return gcd(b, a % b);
}
 
// method to find maximum collinear point
function maxPointOnSameLine(points){
    let N = points.length;
    if (N < 2){
        return N;
    }       
 
    let maxPoint = 0;
    let curMax, overlapPoints, verticalPoints;
 
    // Creating a map for storing the data.
    let slopeMap = new Map();
 
    // looping for each point
    for (let i = 0; i < N; i++)
    {
        curMax = 0;
        overlapPoints = 0;
        verticalPoints = 0;
         
        // looping from i + 1 to ignore same pair again
        for (let j = i + 1; j < N; j++)
        {
            // If both point are equal then just
            // increase overlapPoint count
            if (points[i] === points[j]){
                overlapPoints++;
            }
             
            // If x co-ordinate is same, then both
            // point are vertical to each other
            else if (points[i][0] === points[j][0]){
                verticalPoints++;
            }
            else{
                let yDif = points[j][1] - points[i][1];
                let xDif = points[j][0] - points[i][0];
                let g = gcd(xDif, yDif);
 
                // reducing the difference by their gcd
                yDif = Math.floor(yDif/g);
                xDif = Math.floor(xDif/g);
                 
                // increasing the frequency of current slope.
                let tmp = [yDif, xDif];
                if(slopeMap.has(tmp.join(''))){
                    slopeMap.set(tmp.join(''), slopeMap.get(tmp.join('')) + 1);
                }
                else{
                    slopeMap.set(tmp.join(''), 1);
                }
                 
                curMax = Math.max(curMax, slopeMap.get(tmp.join('')));
            }
             
            curMax = Math.max(curMax, verticalPoints);
        }
 
        // updating global maximum by current point's maximum
        maxPoint = Math.max(maxPoint, curMax + overlapPoints + 1);
         
        // printf("maximum collinear point
        // which contains current point
        // are : %d\n", curMax + overlapPoints + 1);
        slopeMap.clear();
    }
    
    return maxPoint;
}
 
// Driver code
{
    let N = 6;
    let arr = [[-1, 1], [0, 0], [1, 1], [2, 2],
                    [3, 3], [3, 4]];
 
    console.log(maxPointOnSameLine(arr));
}
 
// The code is contributed by Gautam goel (gautamgoel962)

4

Complejidad de tiempo: O (n ² logn), donde n indica la longitud de la string.
Espacio Auxiliar: O(n).

Este artículo es una contribución de 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.