Explanation

Because n≤300n \le 300 we can naively go through all pairs of points and check how many other points are collinear with them. Three points AA, BB, and CC are collinear if and only if ABAB has the same slope as 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}

In practice you'll find this formula in a product form to avoid dealing with floating-point values.

Implementation

Time Complexity: O(N3)\mathcal{O}(N^3)

C++

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++) {

Java

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];

Python

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

Efficient Solution

We can take a point AA and compute the slopes of all lines connecting AA to the other points. Two different points lie on the same line if they share the same slope. In this way, we can determine the maximum number of points lying on the same straight line with respect to AA.

We perform this for all other points.

Implementation

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

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

Python

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):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum