Sweep-Line Algorithms

from typing import NamedTuple, Optional

class Point(NamedTuple):
  """
    A point in the plane.\n
  """
  x: float
  y: float

class Segment(NamedTuple):
  """
    A line segment between two endpoints.\n
  """
  start: Point
  end: Point

def _orientation(first: Point, second: Point, third: Point) -> int:
  """
    Sign of the cross product of (second - first) and (third - first):\n
    +1 counter-clockwise, -1 clockwise, 0 collinear.\n
  """
  # signed area of the triangle; its sign is the turn direction.
  cross: float = (
    (second.x - first.x) * (third.y - first.y)
    - (second.y - first.y) * (third.x - first.x)
  )
  if cross > 0:
    return 1
  if cross < 0:
    return -1
  return 0

def _on_segment(point: Point, segment: Segment) -> bool:
  """
    Whether `point`, known collinear with `segment`, lies within its box.\n
  """
  return (
    min(segment.start.x, segment.end.x) <= point.x
    <= max(segment.start.x, segment.end.x)
    and min(segment.start.y, segment.end.y) <= point.y
    <= max(segment.start.y, segment.end.y)
  )

def segments_cross(first: Segment, second: Segment) -> bool:
  """
    Whether two segments intersect, including collinear overlap and shared\n
    endpoints. Uses the standard four-orientation straddle test.\n
  """
  orient_a: int = _orientation(first.start, first.end, second.start)
  orient_b: int = _orientation(first.start, first.end, second.end)
  orient_c: int = _orientation(second.start, second.end, first.start)
  orient_d: int = _orientation(second.start, second.end, first.end)

  # general case: each segment straddles the line through the other.
  if orient_a != orient_b and orient_c != orient_d:
    return True

  # collinear-and-overlapping special cases.
  if orient_a == 0 and _on_segment(second.start, first):
    return True
  if orient_b == 0 and _on_segment(second.end, first):
    return True
  if orient_c == 0 and _on_segment(first.start, second):
    return True
  if orient_d == 0 and _on_segment(first.end, second):
    return True
  return False

def _y_at(segment: Segment, x: float) -> float:
  """
    The y-coordinate where `segment` meets the vertical line at `x`.\n
    For a vertical segment, returns its lower endpoint's y.\n
  """
  start, end = segment.start, segment.end
  if start.x == end.x:
    return min(start.y, end.y)

  # interpolate along the segment's slope to the sweep line.
  slope: float = (end.y - start.y) / (end.x - start.x)
  return start.y + slope * (x - start.x)

def _crossing_point(first: Segment, second: Segment) -> Optional[Point]:
  """
    The intersection point of two non-parallel segments, if they meet at a\n
    single point; otherwise None (parallel, collinear, or non-crossing).\n
  """
  # endpoint differences along each axis, per Cramer's rule.
  x_diff: tuple[float, float] = (
    first.start.x - first.end.x,
    second.start.x - second.end.x,
  )
  y_diff: tuple[float, float] = (
    first.start.y - first.end.y,
    second.start.y - second.end.y,
  )

  # a zero determinant means the lines are parallel (no single crossing).
  denominator: float = x_diff[0] * y_diff[1] - x_diff[1] * y_diff[0]
  if denominator == 0:
    return None

  # 2x2 cross terms feed the line-intersection formula.
  cross_first: float = (
    first.start.x * first.end.y - first.start.y * first.end.x
  )
  cross_second: float = (
    second.start.x * second.end.y - second.start.y * second.end.x
  )

  # solve for the line crossing, then keep it only if it lies on both segments.
  point_x: float = (
    cross_first * x_diff[1] - x_diff[0] * cross_second
  ) / denominator
  point_y: float = (
    cross_first * y_diff[1] - y_diff[0] * cross_second
  ) / denominator
  point = Point(point_x, point_y)
  if _on_segment(point, first) and _on_segment(point, second):
    return point
  return None

def report_intersections(
  segments: list[Segment],
) -> list[tuple[int, int]]:
  """
    Every pair of indices `(i, j)` with `i < j` whose segments intersect.\n
    Sweeps left to right over endpoint and computed-crossing events, keeping\n
    the active segments ordered by their y at the sweep line and testing only\n
    pairs made newly adjacent. Returns pairs sorted ascending.\n
    Assumes general position (no vertical or collinear segments); the\n
    references handle those degeneracies in full.\n
  """
  found: set[tuple[int, int]] = set()
  active: list[int] = []

  def order_key(index: int, x: float) -> float:
    return _y_at(segments[index], x)

  def record(first_index: int, second_index: int) -> None:
    """
      Test a pair, recording it on a true crossing.\n
    """
    low, high = sorted((first_index, second_index))
    if segments_cross(segments[low], segments[high]):
      found.add((low, high))

  # the sweep stops at every x where the y-order can change: endpoints and
  # pairwise crossings. Stops are kept sorted so that between consecutive stops
  # the order of the active set is fixed; a crossing pair becomes adjacent in
  # the stop immediately before their crossing, so testing neighbours at the
  # midpoint of every gap catches it.
  # record each segment's x-span and seed the stops with its endpoints.
  start_x: dict[int, float] = {}
  end_x: dict[int, float] = {}
  stops: set[float] = set()
  for index, segment in enumerate(segments):
    left, right = sorted((segment.start, segment.end))
    start_x[index] = left.x
    end_x[index] = right.x
    stops.add(left.x)
    stops.add(right.x)

  # add every pairwise crossing x so the order can change at it.
  for first in range(len(segments)):
    for second in range(first + 1, len(segments)):
      point = _crossing_point(segments[first], segments[second])
      if point is not None:
        stops.add(point.x)

  ordered_stops: list[float] = sorted(stops)
  for position, stop in enumerate(ordered_stops):

    # refresh membership: a segment is active across [start_x, end_x].
    active = [
      index
      for index in range(len(segments))
      if start_x[index] <= stop <= end_x[index]
    ]

    # sample the order at the stop and just to either side of it: the order
    # just-left exposes pairs about to cross, the stop catches concurrent
    # crossings, and just-right catches pairs that have just swapped. Testing
    # adjacent pairs in each sampled order covers every crossing among
    # non-vertical segments in general position.
    samples: list[float] = [stop]
    if position > 0:
      samples.append((ordered_stops[position - 1] + stop) / 2)
    if position + 1 < len(ordered_stops):
      samples.append((stop + ordered_stops[position + 1]) / 2)

    # at each sample, order the active set by y and test adjacent pairs.
    for sample_x in samples:
      active.sort(key=lambda index: order_key(index, sample_x))
      for adjacent in range(len(active) - 1):
        record(active[adjacent], active[adjacent + 1])

  return sorted(found)

def report_intersections_naive(
  segments: list[Segment],
) -> list[tuple[int, int]]:
  """
    Brute-force O(n^2) reference: test every pair directly.\n
  """
  # test every i < j pair directly.
  found: list[tuple[int, int]] = []
  for first in range(len(segments)):
    for second in range(first + 1, len(segments)):
      if segments_cross(segments[first], segments[second]):
        found.append((first, second))
  return found

import math
from bisect import insort
from typing import NamedTuple, Optional, Sequence

class Point(NamedTuple):
  """
    A point in the plane.\n
  """
  x: float
  y: float

def _distance(first: Point, second: Point) -> float:
  """
    Euclidean distance between two points.\n
  """
  return math.hypot(first.x - second.x, first.y - second.y)

def closest_pair(points: Sequence[Point]) -> Optional[tuple[Point, Point]]:
  """
    The two distinct points at minimum Euclidean distance, or None if fewer\n
    than two points are given. Ties resolve to the first pair encountered.\n
  """
  if len(points) < 2:
    return None

  # sweep order is left-to-right, ties by y.
  by_x: list[Point] = sorted(points, key=lambda point: (point.x, point.y))
  best_distance: float = math.inf
  best_pair: Optional[tuple[Point, Point]] = None

  # the active strip, holding each survivor as a (y, x) key so it stays sorted
  # by y and a y-window is a contiguous slice; insort keeps it ordered.
  strip: list[tuple[float, float]] = []
  left_edge: int = 0

  for current in by_x:

    # evict every point more than `best_distance` to the left in x; once the
    # best shrinks these can never participate again.
    while (
      left_edge < len(strip)
      and current.x - by_x[left_edge].x > best_distance
    ):
      strip.remove((by_x[left_edge].y, by_x[left_edge].x))
      left_edge += 1

    # only survivors within `best_distance` in y can beat the current best.
    start: int = _lower_bound(strip, current.y - best_distance)
    stop: int = _lower_bound(strip, current.y + best_distance)
    for candidate_y, candidate_x in strip[start:stop + 1]:
      candidate = Point(candidate_x, candidate_y)
      separation: float = _distance(current, candidate)
      if separation < best_distance:
        best_distance = separation
        best_pair = (candidate, current)

    # admit the current point to the strip for later points to query.
    insort(strip, (current.y, current.x))

  return best_pair

def _lower_bound(strip: list[tuple[float, float]], target_y: float) -> int:
  """
    First index in the y-sorted strip whose y is not less than `target_y`.\n
  """
  low: int = 0
  high: int = len(strip)

  # binary search on the y-key of each strip entry.
  while low < high:
    middle: int = (low + high) // 2
    if strip[middle][0] < target_y:
      low = middle + 1
    else:
      high = middle
  return low

def closest_pair_naive(
  points: Sequence[Point],
) -> Optional[tuple[Point, Point]]:
  """
    Brute-force O(n^2) reference: the closest of every pair.\n
  """
  if len(points) < 2:
    return None

  best_distance: float = math.inf
  best_pair: Optional[tuple[Point, Point]] = None

  # keep the closest of every distinct pair.
  for first in range(len(points)):
    for second in range(first + 1, len(points)):
      separation: float = _distance(points[first], points[second])
      if separation < best_distance:
        best_distance = separation
        best_pair = (points[first], points[second])
  return best_pair

from typing import NamedTuple, Sequence

class Interval(NamedTuple):
  """
    A half-open interval [low, high): covers low up to but not including high.\n
  """
  low: float
  high: float

class CoverageSegment(NamedTuple):
  """
    A maximal half-open run [low, high) over which exactly `multiplicity`\n
    intervals overlap.\n
  """
  low: float
  high: float
  multiplicity: int

def max_overlap(intervals: Sequence[Interval]) -> int:
  """
    The largest number of intervals covering any single coordinate.\n
    Ties at a shared coordinate break with -1 (ends) before +1 (starts) so a\n
    half-open endpoint touch is not counted as an overlap.\n
  """
  # +1 at each start, -1 at each end of a non-empty interval.
  events: list[tuple[float, int]] = []
  for interval in intervals:
    if interval.low < interval.high:
      events.append((interval.low, +1))
      events.append((interval.high, -1))

  # at equal coordinate, -1 sorts before +1 because -1 < +1.
  events.sort()

  # the running sum is the live coverage; track its peak.
  current: int = 0
  best: int = 0
  for _, delta in events:
    current += delta
    best = max(best, current)
  return best

def coverage_profile(
  intervals: Sequence[Interval],
) -> list[CoverageSegment]:
  """
    The coverage count over every maximal run of coordinates, in order.\n
    Only covered runs (count > 0) are emitted, and adjacent runs with equal\n
    count are merged into one segment.\n
  """
  # +1 at each start, -1 at each end of a non-empty interval.
  events: list[tuple[float, int]] = []
  for interval in intervals:
    if interval.low < interval.high:
      events.append((interval.low, +1))
      events.append((interval.high, -1))
  if not events:
    return []
  events.sort()

  segments: list[CoverageSegment] = []
  current: int = 0
  index: int = 0
  while index < len(events):
    coordinate: float = events[index][0]

    # apply every event at this exact coordinate before reading the count.
    while index < len(events) and events[index][0] == coordinate:
      current += events[index][1]
      index += 1

    # the count `current` now holds from `coordinate` up to the next one.
    if current > 0 and index < len(events):
      next_coordinate: float = events[index][0]

      # extend the previous run if it abuts at the same count; else open one.
      mergeable: bool = bool(segments) and (
        segments[-1].multiplicity == current
        and segments[-1].high == coordinate
      )
      if mergeable:
        segments[-1] = CoverageSegment(
          segments[-1].low, next_coordinate, current
        )
      else:
        segments.append(
          CoverageSegment(coordinate, next_coordinate, current)
        )
  return segments

def max_overlap_naive(intervals: Sequence[Interval]) -> int:
  """
    Brute-force reference: at each distinct start coordinate, count the\n
    intervals covering it.\n
  """
  # every distinct start is a candidate for the peak overlap.
  coordinates: set[float] = {
    interval.low for interval in intervals if interval.low < interval.high
  }

  # count the intervals covering each candidate and keep the largest.
  best: int = 0
  for coordinate in coordinates:
    covering: int = sum(
      1
      for interval in intervals
      if interval.low <= coordinate < interval.high
    )
    best = max(best, covering)
  return best

import heapq
from collections import Counter
from typing import NamedTuple, Sequence

class Building(NamedTuple):
  """
    An axis-aligned building from x=left to x=right with the given height,\n
    its base on the ground line y=0.\n
  """
  left: float
  right: float
  height: float

class KeyPoint(NamedTuple):
  """
    A skyline key point: the silhouette height becomes `height` at x.\n
  """
  x: float
  height: float

class _ActiveHeights:
  """
    A multiset of active heights supporting max and lazy removal.\n
    The heap stores negated heights for a max-view; a Counter records pending\n
    removals so a popped-but-deleted height can be skipped on the next peek.\n
  """

  def __init__(self) -> None:
    self._heap: list[float] = [0.0]
    self._pending: Counter[float] = Counter()

  def add(self, height: float) -> None:
    """
      Insert one copy of `height`.\n
    """
    heapq.heappush(self._heap, -height)

  def remove(self, height: float) -> None:
    """
      Mark one copy of `height` for lazy deletion.\n
    """
    self._pending[height] += 1

  def maximum(self) -> float:
    """
      The largest active height, discarding any lazily-deleted tops first.\n
    """
    # drop tops that were marked for deletion before reading the max.
    while self._pending[-self._heap[0]] > 0:
      self._pending[-self._heap[0]] -= 1
      heapq.heappop(self._heap)
    return -self._heap[0]

def skyline(buildings: Sequence[Building]) -> list[KeyPoint]:
  """
    The silhouette of the union of `buildings` as left-to-right key points,\n
    each marking where the outline height changes. The final point returns\n
    the outline to the ground (height 0).\n
  """
  events: list[tuple[float, int, float]] = []
  for building in buildings:
    if building.left < building.right and building.height > 0:

      # at equal x, taller starts sort before shorter starts (kind, then the
      # negated height); a start (kind 0) sorts before an end (kind 1) so a
      # touching neighbour does not dip the outline to ground.
      events.append((building.left, 0, -building.height))
      events.append((building.right, 1, building.height))
  events.sort()

  active = _ActiveHeights()
  result: list[KeyPoint] = []
  previous_height: float = 0.0

  index: int = 0
  while index < len(events):
    coordinate: float = events[index][0]

    # process every event sharing this x before reading the outline height.
    while index < len(events) and events[index][0] == coordinate:
      _, kind, signed_height = events[index]
      if kind == 0:
        active.add(-signed_height)
      else:
        active.remove(signed_height)
      index += 1

    # emit a key point wherever the running max changes the outline height.
    current_height: float = active.maximum()
    if current_height != previous_height:
      result.append(KeyPoint(coordinate, current_height))
      previous_height = current_height
  return result

def skyline_naive(buildings: Sequence[Building]) -> list[KeyPoint]:
  """
    Brute-force reference: sample the outline height between consecutive\n
    distinct x-coordinates and emit a key point wherever it changes.\n
  """
  # every building edge is a candidate x for an outline change.
  coordinates: list[float] = sorted(
    {building.left for building in buildings if building.height > 0}
    | {building.right for building in buildings if building.height > 0}
  )

  result: list[KeyPoint] = []
  previous_height: float = 0.0
  for coordinate in coordinates:

    # the outline height here is the tallest building covering this x.
    current_height: float = 0.0
    for building in buildings:
      if building.left <= coordinate < building.right:
        current_height = max(current_height, building.height)

    # record a key point only where that height changes.
    if current_height != previous_height:
      result.append(KeyPoint(coordinate, current_height))
      previous_height = current_height
  return result

from bisect import bisect_left
from typing import NamedTuple, Sequence

class Rectangle(NamedTuple):
  """
    An axis-aligned rectangle spanning [x1, x2] by [y1, y2].\n
  """
  x1: float
  y1: float
  x2: float
  y2: float

class _CoverageTree:
  """
    A segment tree over the elementary y-intervals between consecutive\n
    compressed coordinates. Each leaf is one elementary interval; a node\n
    tracks how many active rectangles cover it (`count`) and the total length\n
    of its span that is covered by at least one (`covered`). Interval updates\n
    add a delta to a span; the root's `covered` is the length under the sweep.\n
  """

  def __init__(self, coordinates: Sequence[float]) -> None:
    self._coordinates: Sequence[float] = coordinates
    cells: int = max(len(coordinates) - 1, 0)
    self._count: list[int] = [0 for _ in range(4 * max(cells, 1))]
    self._covered: list[float] = [0.0 for _ in range(4 * max(cells, 1))]
    self._cells: int = cells

  def update(self, low_index: int, high_index: int, delta: int) -> None:
    """
      Add `delta` to every elementary interval in the coordinate range\n
      [low_index, high_index).\n
    """
    if self._cells > 0:
      self._update(1, 0, self._cells - 1, low_index, high_index - 1, delta)

  def _update(
    self,
    node: int,
    node_low: int,
    node_high: int,
    target_low: int,
    target_high: int,
    delta: int,
  ) -> None:
    # node's span lies entirely outside the target range.
    if target_low > node_high or target_high < node_low:
      return

    # node's span lies entirely inside: stamp the delta on its count.
    if target_low <= node_low and node_high <= target_high:
      self._count[node] += delta

    # partial overlap: split at the midpoint and recurse into both halves.
    else:
      middle: int = (node_low + node_high) // 2
      self._update(2 * node, node_low, middle, target_low, target_high, delta)
      self._update(
        2 * node + 1, middle + 1, node_high, target_low, target_high, delta
      )

    self._refresh(node, node_low, node_high)

  def _refresh(self, node: int, node_low: int, node_high: int) -> None:
    """
      Recompute a node's covered length from its own count and children.\n
    """
    if self._count[node] > 0:
      self._covered[node] = (
        self._coordinates[node_high + 1] - self._coordinates[node_low]
      )
    elif node_low == node_high:
      self._covered[node] = 0.0
    else:
      self._covered[node] = (
        self._covered[2 * node] + self._covered[2 * node + 1]
      )

  @property
  def covered(self) -> float:
    """
      Total y-length covered by at least one active rectangle.\n
    """
    return self._covered[1] if self._cells > 0 else 0.0

class _Edge(NamedTuple):
  """
    A vertical edge of a rectangle: the x at which it occurs, the y-span it\n
    affects, and the +1 (left edge) or -1 (right edge) it contributes.\n
  """
  x: float
  y_low: float
  y_high: float
  delta: int

def union_area(rectangles: Sequence[Rectangle]) -> float:
  """
    The total area covered by the union of `rectangles` (overlaps counted\n
    once). Returns 0 for an empty input.\n
  """
  # split each non-degenerate rectangle into a +1 left edge and -1 right edge.
  edges: list[_Edge] = []
  y_values: list[float] = []
  for rectangle in rectangles:
    if rectangle.x1 < rectangle.x2 and rectangle.y1 < rectangle.y2:
      edges.append(_Edge(rectangle.x1, rectangle.y1, rectangle.y2, +1))
      edges.append(_Edge(rectangle.x2, rectangle.y1, rectangle.y2, -1))
      y_values.append(rectangle.y1)
      y_values.append(rectangle.y2)
  if not edges:
    return 0.0

  # compress the y-axis and sweep the edges left to right.
  compressed: list[float] = sorted(set(y_values))
  tree = _CoverageTree(compressed)
  edges.sort(key=lambda edge: edge.x)

  area: float = 0.0
  previous_x: float = edges[0].x
  for edge in edges:

    # accumulate the slab [previous_x, edge.x): covered y-length times width.
    area += tree.covered * (edge.x - previous_x)
    previous_x = edge.x

    # apply this edge's +1/-1 over its compressed y-range.
    low_index: int = bisect_left(compressed, edge.y_low)
    high_index: int = bisect_left(compressed, edge.y_high)
    tree.update(low_index, high_index, edge.delta)
  return area

def union_area_naive(
  rectangles: Sequence[Rectangle],
  precision: int = 0,
) -> float:
  """
    Brute-force reference: compress both axes into a grid of cells and sum the\n
    area of every cell covered by at least one rectangle.\n
  """
  # compress both axes into the grid of cell boundaries.
  x_values: list[float] = sorted(
    {rectangle.x1 for rectangle in rectangles}
    | {rectangle.x2 for rectangle in rectangles}
  )
  y_values: list[float] = sorted(
    {rectangle.y1 for rectangle in rectangles}
    | {rectangle.y2 for rectangle in rectangles}
  )

  area: float = 0.0
  for column in range(len(x_values) - 1):
    cell_x1: float = x_values[column]
    cell_x2: float = x_values[column + 1]

    for row in range(len(y_values) - 1):
      cell_y1: float = y_values[row]
      cell_y2: float = y_values[row + 1]

      # add a cell's area if its center sits inside any rectangle.
      mid_x: float = (cell_x1 + cell_x2) / 2
      mid_y: float = (cell_y1 + cell_y2) / 2
      for rectangle in rectangles:
        if (
          rectangle.x1 <= mid_x <= rectangle.x2
          and rectangle.y1 <= mid_y <= rectangle.y2
        ):
          area += (cell_x2 - cell_x1) * (cell_y2 - cell_y1)
          break
  return round(area, precision) if precision else area