Skip to Content
CTRL K

Max Points on a Line

Explicación

Como n≤300n \le 300, podemos recorrer de forma naive todos los pares de puntos y comprobar cuántos otros puntos son colineales con ellos. Tres puntos AA, BB y CC son colineales si y solo si ABAB tiene la misma pendiente que BCBC:

Ay−ByAx−Bx=By−CyBx−Cx \frac{A_y-B_y}{A_x-B_x}=\frac{B_y-C_y}{B_x-C_x}

En la práctica, esta fórmula se usa en forma de producto para evitar lidiar con valores de punto flotante.

Implementación

Complejidad temporal: O(N3)\mathcal{O}(N^3)

class Solution {
  public:
	int maxPoints(vector<vector<int>> &points) {
		if (points.size() <= 2) { return points.size(); }
 
		int ans = 0;
		for (int i = 0; i < points.size(); i++) {
			for (int j = i + 1; j < points.size(); j++) {
				int p = 2;  // the 2 points are collinear with themselves
				for (int k = j + 1; k < points.size(); k++) {
					int dx1 = points[i][0] - points[k][0],
					    dx2 = points[j][0] - points[i][0];
					int dy1 = points[i][1] - points[k][1],
					    dy2 = points[j][1] - points[i][1];
					// Check if dy1 / dx1 = dy2 / dx2
					// Which is the same as: dy1 * dx2 = dy2 * dx1
					if (dy1 * dx2 == dy2 * dx1) { p++; }
				}
 
				ans = max(ans, p);
			}
		}
 
		return ans;
	}
};
class Solution {
	public int maxPoints(int[][] points) {
		if (points.length <= 2) { return points.length; }
 
		int ans = 0;
		for (int i = 0; i < points.length; i++) {
			for (int j = i + 1; j < points.length; j++) {
				int p = 2;  // the 2 points are collinear with themselves
				for (int k = j + 1; k < points.length; k++) {
					int dx1 = points[i][0] - points[k][0];
					int dx2 = points[j][0] - points[i][0];
					int dy1 = points[i][1] - points[k][1];
					int dy2 = points[j][1] - points[i][1];
					// Check if dy1 / dx1 = dy2 / dx2
					// Which is the same as: dy1 * dx2 = dy2 * dx1
					if (dy1 * dx2 == dy2 * dx1) { p++; }
				}
 
				ans = Math.max(ans, p);
			}
		}
 
		return ans;
	}
}
class Solution:
	def maxPoints(self, points: List[List[int]]) -> int:
		n = len(points)
		if n <= 2:
			return n
 
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				p = 2  # the 2 points are collinear with themselves
				for k in range(j + 1, n):
					dx1 = points[i][0] - points[k][0]
					dx2 = points[j][0] - points[i][0]
					dy1 = points[i][1] - points[k][1]
					dy2 = points[j][1] - points[i][1]
 
					# Check if dy1 / dx1 = dy2 / dx2
					# Which is the same as: dy1 * dx2 = dy2 * dx1
					if dy1 * dx2 == dy2 * dx1:
						p += 1
 
				ans = max(ans, p)
 
		return ans

Solución eficiente

Podemos tomar un punto AA y calcular las pendientes de todas las rectas que conectan AA con los demás puntos. Dos puntos distintos están sobre la misma recta si comparten la misma pendiente. De esta forma, podemos determinar el máximo número de puntos que yacen sobre la misma recta respecto de AA.

Hacemos esto para todos los demás puntos.

Implementación

Complejidad temporal: O(N2)\mathcal{O}(N^2)

class Solution {
  public:
	int maxPoints(vector<vector<int>> &points) {
		int n = (int)points.size();
		int res = 0;
		for (int i = 0; i < n; i++) {
			unordered_map<float, int> slope_count;
			for (int j = i + 1; j < n; j++) {
				float slope = 0.0;
				if (points[i][0] - points[j][0] == 0) {  // avoid division by 0
					slope = INT_MAX;
				} else {
					slope = float(points[i][1] - points[j][1]) /
					        float(points[i][0] - points[j][0]);
				}
 
				slope_count[slope]++;
			}
			for (auto &[_, pt_num] : slope_count) { res = max(res, pt_num); }
		}
 
		return res + 1;
	}
};
from collections import defaultdict
 
 
class Solution:
	def maxPoints(self, points: List[List[int]]) -> int:
		n = len(points)
		res = 0
		for i in range(n):
			slope_count = defaultdict(int)
			for j in range(i + 1, n):
				if points[i][0] == points[j][0]:  # avoid division by zero
					slope = float("inf")
				else:
					slope = (points[i][1] - points[j][1]) / (
						points[i][0] - points[j][0]
					)
 
				slope_count[slope] += 1
 
			res = max(res, max(slope_count.values(), default=0))
 
		return res + 1
Fundamentos