7.3.8 Maximum Collinear Points

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/*

Given a set of points with integer coordinates, compute the maximum number of points that lie on one
line. For every anchor point, normalize the direction vector to every other point by dividing by
`gcd(abs(dx), abs(dy))` and choosing a canonical sign; equal normalized directions from the same
anchor are collinear with it.

- `max_collinear_points(p)` returns the largest number of collinear points. Duplicate points are
  counted as separate input points.

Overflow warning: coordinate differences and their absolute values must fit in `int64_t`.

Time Complexity:
- O(n^2 log n) per call, where $n$ is the number of points.

Space Complexity:
- O(n) auxiliary.

*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <map>
#include <numeric>
#include <utility>
#include <vector>

struct Point {
  int64_t x, y;
  Point(int64_t x = 0, int64_t y = 0) : x(x), y(y) {}
  bool operator==(const Point &p) const { return x == p.x && y == p.y; }
};

int max_collinear_points(const std::vector<Point> &p) {
  int n = static_cast<int>(p.size()), ans = std::min(n, 1);
  for (int i = 0; i < n; i++) {
    std::map<std::pair<int64_t, int64_t>, int> cnt;
    int duplicates = 0, best = 0;
    for (int j = 0; j < n; j++) {
      if (i == j) {
        continue;
      }
      int64_t dx = p[j].x - p[i].x, dy = p[j].y - p[i].y;  // Overflow warning.
      if (dx == 0 && dy == 0) {
        duplicates++;
        continue;
      }
      int64_t g = std::gcd(std::abs(dx), std::abs(dy));
      dx /= g;
      dy /= g;
      if (dx < 0 || (dx == 0 && dy < 0)) {
        dx = -dx;
        dy = -dy;
      }
      best = std::max(best, ++cnt[{dx, dy}]);
    }
    ans = std::max(ans, best + duplicates + 1);
  }
  return ans;
}

/*** Example Usage ***/

using namespace std;

int main() {
  vector<Point> p{{0, 0}, {1, 1}, {2, 2}, {3, 5}, {4, 6}, {3, 3}};
  assert(max_collinear_points(p) == 4);
  p.push_back(Point(1, 1));
  assert(max_collinear_points(p) == 5);
  assert(max_collinear_points({}) == 0);
  assert(max_collinear_points({Point(2, 3)}) == 1);
  return 0;
}