Skip to content

2152. Minimum Number of Lines to Cover Points 👍

  • Time: $O(n^3 \cdot 2^n)$
  • Space: $O(n^3 \cdot 2^n)$
 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
class Solution {
 public:
  int minimumLines(vector<vector<int>>& points) {
    const int allCovered = (1 << points.size()) - 1;
    return dfs(points, 0, allCovered, vector<int>(allCovered, -1));
  }

 private:
  int dfs(const vector<vector<int>>& points, int covered, int allCovered,
          vector<int>&& mem) {
    if (covered == allCovered)
      return 0;
    if (mem[covered] != -1)
      return mem[covered];

    const int n = points.size();
    int ans = n / 2 + (n & 1);

    for (int i = 0; i < n; ++i) {
      if (covered >> i & 1)
        continue;
      for (int j = 0; j < n; ++j) {
        if (i == j)
          continue;
        // Connect the points[i] with the points[j].
        int newCovered = covered | 1 << i | 1 << j;
        // Mark the points covered by this line.
        const pair<int, int> slope = getSlope(points[i], points[j]);
        for (int k = 0; k < n; ++k)
          if (getSlope(points[i], points[k]) == slope)
            newCovered |= 1 << k;
        ans = min(ans, 1 + dfs(points, newCovered, allCovered, std::move(mem)));
      }
    }

    return mem[covered] = ans;
  }

  pair<int, int> getSlope(const vector<int>& p, const vector<int>& q) {
    const int dx = p[0] - q[0];
    const int dy = p[1] - q[1];
    if (dx == 0)
      return {0, p[0]};
    if (dy == 0)
      return {p[1], 0};
    const int d = __gcd(dx, dy);
    const int x = dx / d;
    const int y = dy / d;
    if (x > 0)
      return {x, y};
    return {-x, -y};
  }
};

 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
class Solution {
  public int minimumLines(int[][] points) {
    final int allCovered = (1 << points.length) - 1;
    int[] mem = new int[allCovered];
    Arrays.fill(mem, -1);
    return dfs(points, 0, allCovered, mem);
  }

  private int dfs(int[][] points, int covered, int allCovered, int[] mem) {
    if (covered == allCovered)
      return 0;
    if (mem[covered] != -1)
      return mem[covered];

    final int n = points.length;
    int ans = n / 2 + ((n & 1) == 1 ? 1 : 0);

    for (int i = 0; i < n; ++i) {
      if ((covered >> i & 1) == 1)
        continue;
      for (int j = 0; j < n; ++j) {
        if (i == j)
          continue;
        // Connect the points[i] with the points[j].
        int newCovered = covered | 1 << i | 1 << j;
        // Mark the points covered by this line.
        Pair<Integer, Integer> slope = getSlope(points[i], points[j]);
        for (int k = 0; k < n; ++k)
          if (getSlope(points[i], points[k]).equals(slope))
            newCovered |= 1 << k;
        ans = Math.min(ans, 1 + dfs(points, newCovered, allCovered, mem));
      }
    }

    return mem[covered] = ans;
  }

  private Pair<Integer, Integer> getSlope(int[] p, int[] q) {
    final int dx = p[0] - q[0];
    final int dy = p[1] - q[1];
    if (dx == 0)
      return new Pair<>(0, p[0]);
    if (dy == 0)
      return new Pair<>(p[1], 0);
    final int d = gcd(dx, dy);
    final int x = dx / d;
    final int y = dy / d;
    return x > 0 ? new Pair<>(x, y) : new Pair<>(-x, -y);
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}

 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
class Solution:
  def minimumLines(self, points: list[list[int]]) -> int:
    n = len(points)
    allCovered = (1 << n) - 1
    maxLines = n // 2 + (n & 1)

    def getSlope(p: list[int], q: list[int]) -> tuple[int, int]:
      dx = p[0] - q[0]
      dy = p[1] - q[1]
      if dx == 0:
        return (0, p[0])
      if dy == 0:
        return (p[1], 0)
      d = gcd(dx, dy)
      x = dx // d
      y = dy // d
      return (x, y) if x > 0 else (-x, -y)

    @functools.lru_cache(None)
    def dfs(covered: int) -> int:
      if covered == allCovered:
        return 0

      ans = maxLines

      for i in range(n):
        if covered >> i & 1:
          continue
        for j in range(n):
          if i == j:
            continue
          # Connect the points[i] with the points[j].
          newCovered = covered | 1 << i | 1 << j
          slope = getSlope(points[i], points[j])
          # Mark the points covered by this line.
          for k in range(n):
            if getSlope(points[i], points[k]) == slope:
              newCovered |= 1 << k
          ans = min(ans, 1 + dfs(newCovered))

      return ans

    return dfs(0)