Misc

Convex hull is a fundamental geometric algorithm that is used to compute the smallest convex polygon that contains a set of points in the plane. The convex hull of a set of points is the smallest convex polygon that encloses all the points. The idea behind the convex hull algorithm is to first sort the points based on their x-coordinate (or y-coordinate, depending on the implementation), and then use a "stack" to keep track of the points that are part of the convex hull. Starting with the leftmost point, we add each point to the stack one by one, making sure to remove any points that would cause the polygon to become non-convex.

Java

public class ConvexHull {
    private static int crossProduct(Point p1, Point p2, Point p3) {
        int x1 = p2.x - p1.x;
        int y1 = p2.y - p1.y;
        int x2 = p3.x - p1.x;
        int y2 = p3.y - p1.y;
        return x1 * y2 - x2 * y1;
    }

    public static List<Point> convexHull(List<Point> points) {
        int n = points.size();
        if (n < 3) return points;
        points.sort((p1, p2) -> {
            if (p1.x != p2.x) return p1.x - p2.x;
            return p1.y - p2.y;
        });
        List<Point> hull = new ArrayList<>();
        hull.add(points.get(0));
        hull.add(points.get(1));
        for (int i = 2; i < n; ++i) {
            Point p = points.get(i);
            while (hull.size() >= 2) {
                Point top = hull.get(hull.size() - 1);
                Point secondTop = hull.get(hull.size() - 2);
                if (crossProduct(secondTop, top, p) <= 0) {
                    hull.remove(hull.size() - 1);
                } else {
                    break;
                }
            }
            hull.add(p);
        }
        return hull;
    }
}

JavaScript

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

function crossProduct(p1, p2, p3) {
  const x1 = p2.x - p1.x;
  const y1 = p2.y - p1.y;
  const x2 = p3.x - p1.x;
  const y2 = p3.y - p1.y;
  return x1 * y2 - x2 * y1;
}

function convexHull(points) {
  const n = points.length;
  if (n < 3) return points;

  points.sort((p1, p2) => {
    if (p1.x !== p2.x) return p1.x - p2.x;
    return p1.y - p2.y;
  });

  const hull = [];
  hull.push(points[0]);
  hull.push(points[1]);

  for (let i = 2; i < n; ++i) {
    const p = points[i];
    while (hull.length >= 2) {
      const top = hull[hull.length - 1];
      const secondTop = hull[hull.length - 2];
      if (crossProduct(secondTop, top, p) <= 0) {
        hull.pop();
      } else {
        break;
      }
    }
    hull.push(p);
  }

  return hull;
}

Python

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def crossProduct(p1, p2, p3):
    x1 = p2.x - p1.x
    y1 = p2.y - p1.y
    x2 = p3.x - p1.x
    y2 = p3.y - p1.y
    return x1 * y2 - x2 * y1

def convexHull(points):
    n = len(points)
    if n < 3:
        return points

    points.sort(key=lambda p: (p.x, p.y))

    hull = [points[0], points[1]]
    for i in range(2, n):
        p = points[i]
        while len(hull) >= 2:
            top = hull[-1]
            secondTop = hull[-2]
            if crossProduct(secondTop, top, p) <= 0:
                hull.pop()
            else:
                break
        hull.append(p)

    return hull

C++

struct Point {
    int x;
    int y;

    Point(int _x, int _y) : x(_x), y(_y) {}
};

int crossProduct(const Point& p1, const Point& p2, const Point& p3) {
    int x1 = p2.x - p1.x;
    int y1 = p2.y - p1.y;
    int x2 = p3.x - p1.x;
    int y2 = p3.y - p1.y;
    return x1 * y2 - x2 * y1;
}

std::vector<Point> convexHull(std::vector<Point>& points) {
    int n = points.size();
    if (n < 3) return points;

    std::sort(points.begin(), points.end(), [](const Point& p1, const Point& p2) {
        if (p1.x != p2.x) return p1.x < p2.x;
        return p1.y < p2.y;
    });

    std::vector<Point> hull;
    hull.push_back(points[0]);
    hull.push_back(points[1]);

    for (int i = 2; i < n; ++i) {
        const Point& p = points[i];
        while (hull.size() >= 2) {
            const Point& top = hull.back();
            const Point& secondTop = hull[hull.size() - 2];
            if (crossProduct(secondTop, top, p) <= 0) {
                hull.pop_back();
            } else {
                break;
            }
        }
        hull.push_back(p);
    }

    return hull;
}

Note that the crossProduct method calculates the cross product of two vectors p1p2 and p1p3, where p1, p2, and p3 are points in 2D space. The sign of the cross product indicates whether p1p3 is to the left or to the right of p1p2. If we have p1p3 to the right of p1p2 we just continue adding the new point, but if we have it on the left that means we have to remove the last point we added since we have a better path now (connecting p1p3 instead p1p2). The time complexity of the algorithm is just that of sorting (O(n logn)).

A sweep line algorithm is a computational geometry technique that involves the use of a moving line, or sweep line, to solve geometric problems. This algorithm is often used to solve problems related to lines and polygons in two-dimensional space.

Java

class Point implements Comparable<Point> {
    double x, y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    // Compare points by x-coordinate
    public int compareTo(Point other) {
        return Double.compare(this.x, other.x);
    }
}

class Pair {
    Point p1, p2;
    double distance;

    Pair(Point p1, Point p2, double distance) {
        this.p1 = p1;
        this.p2 = p2;
        this.distance = distance;
    }
}

public class ClosestPair {
    public static Pair closestPair(Point[] points) {
        Arrays.sort(points); // sort points by x-coordinate
        TreeSet<Point> activeSet = new TreeSet<>((p1, p2) -> Double.compare(p1.y, p2.y));
        int j = 0;
        double bestDistance = Double.POSITIVE_INFINITY;
        Pair bestPair = null;
        for (int i = 0; i < points.length; i++) {
            Point p1 = points[i];
            while (j < i && points[j].x < p1.x - bestDistance) {
                activeSet.remove(points[j]);
                j++;
            }
            Point lo = new Point(p1.x - bestDistance, p1.y - bestDistance);
            Point hi = new Point(p1.x + bestDistance, p1.y + bestDistance);
            for (Point p2 : activeSet.subSet(lo, hi)) {
                double distance = distance(p1, p2);
                if (distance < bestDistance) {
                    bestDistance = distance;
                    bestPair = new Pair(p1, p2, distance);
                }
            }
            activeSet.add(p1);
        }
        return bestPair;
    }

    private static double distance(Point p1, Point p2) {
        double dx = p1.x - p2.x;
        double dy = p1.y - p2.y;
        return Math.sqrt(dx*dx + dy*dy);
    }
}

JavaScript

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  compareTo(other) {
    return this.x - other.x;
  }
}

class Pair {
  constructor(p1, p2, distance) {
    this.p1 = p1;
    this.p2 = p2;
    this.distance = distance;
  }
}

class ClosestPair {
  static closestPair(points) {
    points.sort((p1, p2) => p1.compareTo(p2));
    const activeSet = new Set();
    let j = 0;
    let bestDistance = Infinity;
    let bestPair = null;

    for (let i = 0; i < points.length; i++) {
      const p1 = points[i];

      while (j < i && points[j].x < p1.x - bestDistance) {
        activeSet.delete(points[j]);
        j++;
      }

      const lo = new Point(p1.x - bestDistance, p1.y - bestDistance);
      const hi = new Point(p1.x + bestDistance, p1.y + bestDistance);

      for (const p2 of activeSet) {
        if (p2.y < lo.y || p2.y > hi.y) continue;

        const distance = this.distance(p1, p2);

        if (distance < bestDistance) {
          bestDistance = distance;
          bestPair = new Pair(p1, p2, distance);
        }
      }

      activeSet.add(p1);
    }

    return bestPair;
  }

  static distance(p1, p2) {
    const dx = p1.x - p2.x;
    const dy = p1.y - p2.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
}

Python

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __lt__(self, other):
        return self.x < other.x

class Pair:
    def __init__(self, p1, p2, distance):
        self.p1 = p1
        self.p2 = p2
        self.distance = distance

class ClosestPair:
    @staticmethod
    def closestPair(points):
        points.sort()
        activeSet = set()
        j = 0
        bestDistance = math.inf
        bestPair = None

        for i in range(len(points)):
            p1 = points[i]

            while j < i and points[j].x < p1.x - bestDistance:
                activeSet.remove(points[j])
                j += 1

            lo = Point(p1.x - bestDistance, p1.y - bestDistance)
            hi = Point(p1.x + bestDistance, p1.y + bestDistance)

            for p2 in activeSet:
                if lo.y <= p2.y <= hi.y:
                    distance = ClosestPair.distance(p1, p2)
                    if distance < bestDistance:
                        bestDistance = distance
                        bestPair = Pair(p1, p2, distance)

            activeSet.add(p1)

        return bestPair

    @staticmethod
    def distance(p1, p2):
        dx = p1.x - p2.x
        dy = p1.y - p2.y
        return math.sqrt(dx * dx + dy * dy)

C++

struct Point {
  double x, y;

  bool operator<(const Point& other) const {
    return x < other.x;
  }
};

struct Pair {
  Point p1, p2;
  double distance;
};

class ClosestPair {
public:
  static Pair closestPair(std::vector<Point>& points) {
    std::sort(points.begin(), points.end());
    std::set<Point, CompareY> activeSet;
    int j = 0;
    double bestDistance = std::numeric_limits<double>::infinity();
    Pair bestPair;

    for (int i = 0; i < points.size(); i++) {
      const Point& p1 = points[i];

      while (j < i && points[j].x < p1.x - bestDistance) {
        activeSet.erase(points[j]);
        j++;
      }

      const Point lo{p1.x - bestDistance, p1.y - bestDistance};
      const Point hi{p1.x + bestDistance, p1.y + bestDistance};

      for (const auto& p2 : activeSet) {
        if (p2.y < lo.y || p2.y > hi.y) continue;

        const double distance = calcDistance(p1, p2);

        if (distance < bestDistance) {
          bestDistance = distance;
          bestPair = {p1, p2, distance};
        }
      }

      activeSet.insert(p1);
    }

    return bestPair;
  }

private:
  struct CompareY {
    bool operator()(const Point& p1, const Point& p2) const {
      return p1.y < p2.y;
    }
  };

  static double calcDistance(const Point& p1, const Point& p2) {
    const double dx = p1.x - p2.x;
    const double dy = p1.y - p2.y;
    return std::sqrt(dx * dx + dy * dy);
  }
};

In this implementation, we use a TreeSet to maintain an "active set" of points that are within the current best distance from the current point being considered. We iterate over the points in order of increasing x-coordinate, and for each point, we remove any points from the active set that are too far to the left to be within the current best distance. We then consider all points in the active set that are within the current best distance to the current point, and update the best pair and best distance if we find a pair of points that is closer than the current best pair. Finally, we add the current point to the active set.

Segment tree for range search/update:

We can represent a segment tree as an array of 2n elements, where n is the size of the original array and a power of two. The nodes of the tree are stored in a top-down order, with the top node being stored at tree[0], its children at tree[1] and tree[2], and so on. The values of the original array are stored in the bottom level of the tree, from tree[n] to tree[2n-1].

In this representation, the parent of a node at tree[k] is located at tree[floor(k/2)], and its left and right children are located at tree[2k] and tree[2k+1], respectively. It should be noted that a node is located at an even position if it is a left child and at an odd position if it is a right child.

Java

public static int sum(int a, int b) {
    a += n; b += n;
    int s = 0;
    while (a <= b) {
        if (a%2 == 1) s += tree[a++];
        if (b%2 == 0) s += tree[b--];
        a /= 2; b /= 2;
    }
    return s;
}

void add(int k, int x) {
    k += n;
    tree[k] += x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2*k]+tree[2*k+1];
    }
}

// can support both search and update with lazy propagation
public static int sum(int a, int b, int k, int x, int y) {
    if (b < x || a > y) return 0;
    if (a <= x && y <= b) return tree[k];
    int d = (x+y)/2;
    return sum(a,b,2*k,x,d) + sum(a,b,2*k+1,d+1,y);
}
int s = sum(a, b, 1, 0, n-1);

JavaScript

function sum(a, b) {
  a += n;
  b += n;
  let s = 0;

  while (a <= b) {
    if (a % 2 === 1) s += tree[a];
    if (b % 2 === 0) s += tree[b];
    a /= 2;
    b /= 2;
  }

  return s;
}

function add(k, x) {
  k += n;
  tree[k] += x;

  for (k /= 2; k >= 1; k /= 2) {
    tree[k] = tree[2 * k] + tree[2 * k + 1];
  }
}

function sumRange(a, b, k, x, y) {
  if (b < x || a > y) return 0;
  if (a <= x && y <= b) return tree[k];
  const d = Math.floor((x + y) / 2);
  return sumRange(a, b, 2 * k, x, d) + sumRange(a, b, 2 * k + 1, d + 1, y);
}

let s = sumRange(a, b, 1, 0, n - 1);

Python

def sum_range(a, b, k, x, y):
    if b < x or a > y:
        return 0
    if a <= x and y <= b:
        return tree[k]
    d = (x + y) // 2
    return (
        sum_range(a, b, 2 * k, x, d)
        + sum_range(a, b, 2 * k + 1, d + 1, y)
    )

def add(k, x):
    k += n
    tree[k] += x

    while k >= 1:
        k //= 2
        tree[k] = tree[2 * k] + tree[2 * k + 1]

s = sum_range(a, b, 1, 0, n - 1)

C++

std::vector<int> tree;
int n;

int sum(int a, int b) {
    a += n;
    b += n;
    int s = 0;

    while (a <= b) {
        if (a % 2 == 1) s += tree[a++];
        if (b % 2 == 0) s += tree[b--];
        a /= 2;
        b /= 2;
    }

    return s;
}

void add(int k, int x) {
    k += n;
    tree[k] += x;

    while (k >= 1) {
        k /= 2;
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

int sumRange(int a, int b, int k, int x, int y) {
    if (b < x || a > y) return 0;
    if (a <= x && y <= b) return tree[k];
    int d = (x + y) / 2;
    return sumRange(a, b, 2 * k, x, d) + sumRange(a, b, 2 * k + 1, d + 1, y);
}

int s = sumRange(a, b, 1, 0, n - 1);