Skip to content

1924. Erect the Fence II 👎

  • Time: $O(n)$
  • Space: $O(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
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
struct Point {
  double x;
  double y;
  Point(double x, double y) : x(x), y(y) {}
};

struct Disk {
  Point center;
  double radius;
  Disk(const Point& center, double radius) : center(center), radius(radius) {}
};

class Solution {
 public:
  vector<double> outerTrees(vector<vector<int>>& trees) {
    vector<Point> points;
    for (int i = 0; i < trees.size(); ++i)
      points.emplace_back(trees[i][0], trees[i][1]);
    Disk disk = welzl(points, 0, {});
    return {disk.center.x, disk.center.y, disk.radius};
  }

 private:
  // Returns the smallest disk that encloses points[i..n).
  // https://en.wikipedia.org/wiki/Smallest-disk_problem#Welzl's_algorithm
  Disk welzl(const vector<Point>& points, int i, vector<Point> planePoints) {
    if (i == points.size() || planePoints.size() == 3)
      return trivial(planePoints);
    Disk disk = welzl(points, i + 1, planePoints);
    if (inside(disk, points[i]))
      return disk;
    return welzl(points, i + 1, addPlanePoint(planePoints, points[i]));
  }

  vector<Point> addPlanePoint(const vector<Point>& planePoints,
                              const Point& point) {
    vector<Point> newPlanePoints(planePoints);
    newPlanePoints.push_back(point);
    return newPlanePoints;
  }
  // Returns the smallest disk that encloses `planePoints`.
  Disk trivial(const vector<Point>& planePoints) {
    if (planePoints.empty())
      return Disk(Point(0, 0), 0);
    if (planePoints.size() == 1)
      return Disk(Point(planePoints[0].x, planePoints[0].y), 0);
    if (planePoints.size() == 2)
      return getDisk(planePoints[0], planePoints[1]);

    Disk disk01 = getDisk(planePoints[0], planePoints[1]);
    if (inside(disk01, planePoints[2]))
      return disk01;

    Disk disk02 = getDisk(planePoints[0], planePoints[2]);
    if (inside(disk02, planePoints[1]))
      return disk02;

    Disk disk12 = getDisk(planePoints[1], planePoints[2]);
    if (inside(disk12, planePoints[0]))
      return disk12;

    return getDisk(planePoints[0], planePoints[1], planePoints[2]);
  }

  // Returns the smallest disk that encloses the points A and B.
  Disk getDisk(const Point& A, const Point& B) {
    const double x = (A.x + B.x) / 2;
    const double y = (A.y + B.y) / 2;
    return Disk(Point(x, y), distance(A, B) / 2);
  }

  // Returns the smallest disk that encloses the points A, B, and C.
  Disk getDisk(const Point& A, const Point& B, const Point& C) {
    // Calculate midpoints.
    Point mAB((A.x + B.x) / 2, (A.y + B.y) / 2);
    Point mBC((B.x + C.x) / 2, (B.y + C.y) / 2);

    // Calculate the slopes and the perpendicular slopes.
    const double slopeAB = (B.y - A.y) / (B.x - A.x);
    const double slopeBC = (C.y - B.y) / (C.x - B.x);
    const double perpSlopeAB = -1 / slopeAB;
    const double perpSlopeBC = -1 / slopeBC;

    // Calculate the center.
    const double x =
        (perpSlopeBC * mBC.x - perpSlopeAB * mAB.x + mAB.y - mBC.y) /
        (perpSlopeBC - perpSlopeAB);
    const double y = perpSlopeAB * (x - mAB.x) + mAB.y;
    Point center(x, y);
    return Disk(center, distance(center, A));
  }

  // Returns true if the point is inside the disk.
  bool inside(Disk disk, Point point) {
    return disk.radius > 0 && distance(disk.center, point) <= disk.radius;
  }

  double distance(Point A, Point B) {
    const double dx = A.x - B.x;
    const double dy = A.y - B.y;
    return sqrt(dx * dx + dy * dy);
  }
};

  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
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
class Point {
  public double x;
  public double y;
  public Point(double x, double y) {
    this.x = x;
    this.y = y;
  }
}

class Disk {
  public Point center;
  public double radius;
  public Disk(Point center, double radius) {
    this.center = center;
    this.radius = radius;
  }
}

class Solution {
  public double[] outerTrees(int[][] trees) {
    Point[] points = new Point[trees.length];
    for (int i = 0; i < trees.length; ++i)
      points[i] = new Point(trees[i][0], trees[i][1]);
    Disk disk = welzl(points, 0, new ArrayList<>());
    return new double[] {disk.center.x, disk.center.y, disk.radius};
  }

  // Returns the smallest disk that encloses points[i..n).
  // https://en.wikipedia.org/wiki/Smallest-disk_problem#Welzl's_algorithm
  private Disk welzl(Point[] points, int i, List<Point> planePoints) {
    if (i == points.length || planePoints.size() == 3)
      return trivial(planePoints);
    Disk disk = welzl(points, i + 1, planePoints);
    if (inside(disk, points[i]))
      return disk;
    return welzl(points, i + 1, addPlanePoints(planePoints, points[i]));
  }

  private List<Point> addPlanePoints(List<Point> planePoints, Point point) {
    List<Point> newPlanePoints = new ArrayList<>(planePoints);
    newPlanePoints.add(point);
    return newPlanePoints;
  }

  // Returns the smallest disk that encloses `planePoints`.
  private Disk trivial(List<Point> planePoints) {
    if (planePoints.isEmpty())
      return null;
    if (planePoints.size() == 1)
      return new Disk(new Point(planePoints.get(0).x, planePoints.get(0).y), 0);
    if (planePoints.size() == 2)
      return getDisk(planePoints.get(0), planePoints.get(1));

    Disk disk01 = getDisk(planePoints.get(0), planePoints.get(1));
    if (inside(disk01, planePoints.get(2)))
      return disk01;

    Disk disk02 = getDisk(planePoints.get(0), planePoints.get(2));
    if (inside(disk02, planePoints.get(1)))
      return disk02;

    Disk disk12 = getDisk(planePoints.get(1), planePoints.get(2));
    if (inside(disk12, planePoints.get(0)))
      return disk12;

    return getDisk(planePoints.get(0), planePoints.get(1), planePoints.get(2));
  }

  // Returns the smallest disk that encloses the points A and B.
  private Disk getDisk(Point A, Point B) {
    final double x = (A.x + B.x) / 2;
    final double y = (A.y + B.y) / 2;
    return new Disk(new Point(x, y), distance(A, B) / 2);
  }

  // Returns the smallest disk that encloses the points A, B, and C.
  private Disk getDisk(Point A, Point B, Point C) {
    // Calculate midpoints.
    Point mAB = new Point((A.x + B.x) / 2, (A.y + B.y) / 2);
    Point mBC = new Point((B.x + C.x) / 2, (B.y + C.y) / 2);

    // Calculate the slopes and the perpendicular slopes.
    final double slopeAB = (B.y - A.y) / (B.x - A.x);
    final double slopeBC = (C.y - B.y) / (C.x - B.x);
    final double perpSlopeAB = -1 / slopeAB;
    final double perpSlopeBC = -1 / slopeBC;

    // Calculate the center.
    final double x =
        (perpSlopeBC * mBC.x - perpSlopeAB * mAB.x + mAB.y - mBC.y) / (perpSlopeBC - perpSlopeAB);
    final double y = perpSlopeAB * (x - mAB.x) + mAB.y;
    Point center = new Point(x, y);
    return new Disk(center, distance(center, A));
  }

  // Returns true if the point is inside the disk.
  private boolean inside(Disk disk, Point point) {
    return disk != null && distance(disk.center, point) <= disk.radius;
  }

  private double distance(Point A, Point B) {
    final double dx = A.x - B.x;
    final double dy = A.y - B.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
}

 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from dataclasses import dataclass


@dataclass(frozen=True)
class Point:
  x: float
  y: float


@dataclass(frozen=True)
class Disk:
  center: Point
  radius: float


class Solution:
  def outerTrees(self, trees: list[list[int]]) -> list[float]:
    points = [Point(x, y) for x, y in trees]
    disk = self._welzl(points, 0, [])
    return [disk.center.x, disk.center.y, disk.radius]

  def _welzl(
      self,
      points: list[Point],
      i: int,
      planePoints: list[Point],
  ) -> Disk:
    """Returns the smallest disk that encloses points[i..n).

    https://en.wikipedia.org/wiki/Smallest-disk_problem#Welzl's_algorithm
    """
    if i == len(points) or len(planePoints) == 3:
      return self._trivial(planePoints)
    disk = self._welzl(points, i + 1, planePoints)
    if self._inside(disk, points[i]):
      return disk
    return self._welzl(points, i + 1, planePoints + [points[i]])

  def _trivial(self, planePoints: list[Point]) -> Disk:
    """Returns the smallest disk that encloses `planePoints`."""
    if len(planePoints) == 0:
      return Disk(Point(0, 0), 0)
    if len(planePoints) == 1:
      return Disk(Point(planePoints[0].x, planePoints[0].y), 0)
    if len(planePoints) == 2:
      return self._getDisk(planePoints[0], planePoints[1])

    disk01 = self._getDisk(planePoints[0], planePoints[1])
    if self._inside(disk01, planePoints[2]):
      return disk01

    disk02 = self._getDisk(planePoints[0], planePoints[2])
    if self._inside(disk02, planePoints[1]):
      return disk02

    disk12 = self._getDisk(planePoints[1], planePoints[2])
    if self._inside(disk12, planePoints[0]):
      return disk12

    return self._getDiskFromThree(
        planePoints[0],
        planePoints[1],
        planePoints[2])

  def _getDisk(self, A: Point, B: Point) -> Disk:
    """Returns the smallest disk that encloses the points A and B."""
    x = (A.x + B.x) / 2
    y = (A.y + B.y) / 2
    return Disk(Point(x, y), self._distance(A, B) / 2)

  def _getDiskFromThree(self, A: Point, B: Point, C: Point) -> Disk:
    """Returns the smallest disk that encloses the points A, B, and C."""
    # Calculate midpoints.
    mAB = Point((A.x + B.x) / 2, (A.y + B.y) / 2)
    mBC = Point((B.x + C.x) / 2, (B.y + C.y) / 2)

    # Calculate the slopes and the perpendicular slopes.
    slopeAB = math.inf if B.x == A.x else (B.y - A.y) / (B.x - A.x)
    slopeBC = math.inf if C.x == B.x else (C.y - B.y) / (C.x - B.x)
    perpSlopeAB = math.inf if slopeAB == 0 else -1 / slopeAB
    perpSlopeBC = math.inf if slopeBC == 0 else -1 / slopeBC

    # Calculate the center.
    x = (perpSlopeBC * mBC.x - perpSlopeAB * mAB.x +
         mAB.y - mBC.y) / (perpSlopeBC - perpSlopeAB)
    y = perpSlopeAB * (x - mAB.x) + mAB.y
    center = Point(x, y)
    return Disk(center, self._distance(center, A))

  def _inside(self, disk: Disk, point: Point) -> bool:
    """Returns True if the point is inside the disk."""
    return disk.radius > 0 and self._distance(disk.center, point) <= disk.radius

  def _distance(self, A: Point, B: Point) -> float:
    dx = A.x - B.x
    dy = A.y - B.y
    return math.sqrt(dx**2 + dy**2)