Skip to content

KINGDOMS

Why Practice This

This is a good geometry problem because the polygons are convex, disjoint-or-nested, and numerous enough that repeated point-in-polygon checks are too slow. The important structural observation is that a vertical sweep line sees a laminar family of intervals.

Recognition Cue

Reach for a sweep-line laminar-family view when:

  • many geometric regions are disjoint-or-nested
  • queries ask for the deepest containing region
  • repeating point-in-polygon against every region is too slow

The strongest smell is:

  • "nested convex polygons plus many point queries"

That often means one sweep position sees a family of ordered intervals.

Problem-Specific Transformation

The polygon-containment story is rewritten as:

  • at one x, each active polygon contributes one vertical interval
  • because polygons are disjoint or nested, these intervals form a laminar order

So the query becomes:

  • among active intervals, find the deepest one whose lower boundary is below the query and whose upper boundary is above it

That turns many expensive geometric membership tests into one ordered active-set problem.

Core Idea

For a fixed x, every active convex polygon intersects the vertical line in one interval:

[lower(x), upper(x)]

Because polygons are either disjoint or nested, these intervals form a laminar family.

So during a left-to-right sweep:

  • maintain all active kingdoms ordered by lower(x)
  • for a query (x, y), take the active kingdom whose lower boundary is the largest one still below y
  • if its upper boundary is also above y, that is the deepest containing kingdom
  • otherwise, climb parent kingdoms until the upper boundary contains y

The containment tree itself can also be built during the sweep:

  • when a polygon starts at its leftmost x
  • its parent is exactly the active polygon immediately below its lower boundary

Complexity

  • preprocessing convex chains: O(total_vertices log total_vertices_per_polygon)
  • sweep: O((N + Q) log N)
  • ancestor climbing per query: O(log N)

This fits the small time limit only because we avoid checking polygons one by one.

Pitfalls / Judge Notes

  • Queries are guaranteed not to lie on polygon borders.
  • Start/end x values are boundary-only positions, so event order matters:
  • remove ending polygons first
  • answer queries
  • insert starting polygons
  • The answer is the deepest kingdom containing the house, not just any containing kingdom.
  • Using long long is necessary for coordinates; use careful comparisons for line-vs-point checks.

Reusable Pattern

Solutions