On this page

Computational Geometry

A delivery app needs to know whether your phone's GPS fix lies inside the zone a restaurant serves. A game needs to know, sixty times a second, whether a bullet's path crosses a wall. A robot vacuum needs the outline of the obstacles it has bumped into. A mapping database needs the area of a lake drawn as a polygon with 40,000 corners. None of these questions involves anything harder than school algebra, and yet each one is a classic source of bugs: wrong answers on edge cases, crashes on "impossible" inputs, and results that change when you move the whole picture by one millimetre.

Computational geometry is the study of algorithms for points, lines, segments and polygons. This lesson builds the core toolkit from a single primitive, the cross product, and shows how to use it exactly: on integer coordinates every test in this lesson is computed with no rounding at all, so it is always right. On top of that primitive we build segment intersection, polygon area, point-in-polygon, two convex hull algorithms, the rotating calipers, and the idea of a sweep line.

This lesson sits in Module 8 (Math). It uses sorting (Merge Sort), a stack (Stacks), and the closest-pair algorithm from Divide & Conquer, which we link rather than repeat. The spatial indexes that make geometry fast on millions of objects (k-d trees, quadtrees, R-trees) are in Spatial Trees.

Why it exists

Before the 1970s, geometric problems on a computer were solved one at a time, inside graphics, CAD and cartography programs. Michael Shamos's 1978 PhD thesis at Yale, Computational Geometry, and the book he wrote with Franco Preparata (1985) turned them into a field with its own algorithms and lower bounds. Two of the results in this lesson come from that era: Ronald Graham's convex hull algorithm (1972, from Bell Labs), and Shamos and Hoey's sweep-line test for crossing segments (1976).

The field exists because geometry has two traps that ordinary programming does not:

  1. Degenerate cases. Three points can be collinear. Two segments can overlap instead of crossing. A ray can pass exactly through a polygon's corner. Textbook formulas silently assume none of this happens; real data (maps snapped to a grid, game levels made of axis-aligned boxes) is full of it.
  2. Rounding. Floating-point arithmetic answers "is this point left of that line?" wrongly when the point is very close to the line. Wrong answers to consistent questions make algorithms contradict themselves: a convex hull program can output a polygon that is not convex, or loop forever.

The cure for both is the same: reduce every decision to the sign of a small determinant, compute that sign exactly, and handle the zero case on purpose.

Pattern triggers

If the problem says or has…Think of…
"is the turn left or right", "clockwise or counter-clockwise", "which side of the line"The orientation test (sign of a cross product)
"do these two segments intersect / touch", "does the path cross a wall"Four orientation tests plus the collinear on-segment check
"area of a polygon" given its corners in orderShoelace formula (signed area)
"is this point inside the polygon / zone / fence"Ray casting (even–odd) or winding number
"smallest fence / rubber band around all points", "outermost points"Convex hull: monotone chain or Graham scan
"farthest pair of points", "diameter", "width of a point set"Convex hull + rotating calipers
"closest pair of points"Divide and conquer, or a sweep with a sorted set (closest pair)
"do any of these segments cross?" with largeSweep line (Shamos–Hoey)
"report all crossings"Bentley–Ottmann sweep
"area covered by the union of rectangles"Sweep over + coordinate compression (+ segment tree)
"lattice points inside a polygon", "integer points on the boundary"Pick's theorem + gcd per edge
"region satisfying all these linear constraints" in 2-DHalf-plane intersection
"max of lines at a point" inside a DPThe convex hull trick (DP Optimizations)
Many points, "which are near this one / in this box"A spatial index (Spatial Trees)

The meta-trigger: the input is coordinates. Before reaching for trigonometry (angles, atan2, sqrt), ask whether the question is really "which side?" or "how much area?". Both are cross products, and both are exact on integers.

Intuition & first principles

Points and vectors

A point is a location: . A vector is a displacement: "3 right, 1 up", written . The difference of two points is a vector: from to is . In code both are pairs of numbers; the distinction is about meaning. We use the standard maths convention: grows to the right and grows up. (Screens usually have growing down, which flips every "left" into "right". Pick one convention and stick to it.)

Two operations on vectors and do almost all the work.

The dot product: "how much do they point the same way?"

where is the angle between them and is the length. The sign tells you the angle without computing it:

  • : angle less than 90°, they point roughly the same way.
  • : perpendicular.
  • : more than 90°, roughly opposite.

Example: . And , so squared distances need no square root: . Compare squared distances whenever you only need "which is closer"; they stay integers.

The cross product: "which way do I turn, and how much area?"

In 2-D, the cross product of two vectors is the single number

where is the angle you rotate counter-clockwise to reach . (It is the -component of the 3-D cross product of and . It is also the determinant of the matrix with rows and .)

Two facts make it the workhorse of the field:

  1. Its sign is the turn direction. Positive: is counter-clockwise from (a left turn). Negative: clockwise (a right turn). Zero: parallel or opposite (collinear).
  2. Its absolute value is an area. is the area of the parallelogram spanned by and , so half of it is the area of the triangle they span.

Example: , . Then : positive, so is a left turn from , and the triangle with sides and has area . Swap them: . The cross product is anti-symmetric.

flowchart LR
    V["Vectors a, b"] --> DOT["dot: ax*bx + ay*by"]
    V --> CROSS["cross: ax*by - ay*bx"]
    DOT --> D1["sign: same way / perpendicular / opposite"]
    DOT --> D2["a dot a = squared length"]
    CROSS --> C1["sign: left turn / collinear / right turn"]
    CROSS --> C2["absolute value = parallelogram area"]

The orientation test (CCW)

Given three points , , , walk from to and then on to . Do you turn left, turn right, or go straight? Compute

  • : is a counter-clockwise (left) turn; lies to the left of the directed line .
  • : clockwise (right) turn; is to the right.
  • : the three points are collinear.

This one function, often called ccw or orient, is the primitive from which every algorithm in this lesson is assembled. Its value is also twice the signed area of triangle .

Tiny example: , . For : , left. For : , right. For : , collinear.

Exact integers versus floating-point epsilon

If the coordinates are integers, cross uses only subtraction and multiplication, so its result is an exact integer. With coordinates up to in absolute value, the differences are up to and the products up to , and the final difference up to , which fits in a signed 64-bit integer (limit about ). So: with , 64-bit integers give the exact sign. Larger coordinates need 128-bit integers (C++ __int128, Java Math.multiplyHigh or BigInteger, Python is unbounded already).

With floating-point coordinates the products are rounded, and the sign can come out wrong when the true value is tiny compared with the rounding error. This is not a theoretical worry. Kettner, Mehlhorn, Pion, Schirra and Yap's "Classroom Examples of Robustness Problems in Geometric Computations" (2008) uses the following experiment, which you can run:

from fractions import Fraction


def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def sign(v):
    return (v > 0) - (v < 0)


u = 2.0 ** -53                      # the gap between adjacent doubles just above 0.5
q, r = (12.0, 12.0), (24.0, 24.0)   # two points on the line y = x
wrong_sign = wrong_zero = 0
for i in range(256):
    for j in range(256):
        p = (0.5 + i * u, 0.5 + j * u)  # every one of these is an exact double
        fast = sign(cross(p, q, r))                                   # floating point
        exact = sign(cross(*[(Fraction(x), Fraction(y)) for x, y in (p, q, r)]))
        if fast != exact:
            if fast == 0:
                wrong_zero += 1
            else:
                wrong_sign += 1
print(wrong_sign, wrong_zero)       # 672 11300  (of 65,536 points)

p = (0.5 + 247 * u, 0.5 + 239 * u)
print(cross(p, q, r))                                                 # 5.684341886080802e-14  (says: left)
print(cross(*[(Fraction(x), Fraction(y)) for x, y in (p, q, r)]))    # -3/281474976710656    (truth: right)

The points and lie on the line . Each is a point within a few billionths of a billionth of , and the question is whether is above or below that line. In double precision, 11,300 of the 65,536 points are reported as exactly collinear when they are not, and 672 get the wrong sign: the program says "left" where the truth is "right". An algorithm that asks "is left of ?" and later "is left of ?" can get contradictory answers, and then a hull can come out non-convex or a triangulation can contain overlapping triangles.

There are four standard responses, best first:

  1. Use integers. If the input is integer (pixels, grid cells, coordinates in centimetres, contest inputs), keep it integer. Every test in this lesson is exact on integers.
  2. Scale to integers. GPS coordinates with 7 decimal places become integers after multiplying by (about 1 cm resolution at the equator). Many GIS systems store fixed-point coordinates for this reason.
  3. Exact or adaptive predicates. Jonathan Shewchuk's "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates" (1997) computes the sign of cross on doubles exactly, paying extra only when the fast estimate is too close to zero to trust. CGAL builds the same idea into its "exact predicates" kernels.
  4. An epsilon. Treat as zero. This is what most quick code does, and it is the weakest option: "collinear" stops being transitive ( nearly collinear and nearly collinear does not make nearly collinear), and the right depends on the scale of the coordinates (the error grows with the size of the products). If you must, make relative to the magnitude of the operands, and accept that decisions near the threshold are arbitrary.

Rule of thumb

Decide with exact integers; compute measurements (lengths, angles, intersection coordinates) in floating point only at the end, when nothing else depends on them. The orientation test is a decision. The intersection point of two segments is a measurement.

Mechanics

1. Segment intersection

Two closed segments and (each includes its endpoints) intersect if they share at least one point. The whole test is four orientations.

General case. The segments properly cross (meet at a single point that is not an endpoint of either) exactly when and are on strictly opposite sides of the line through , and and are on strictly opposite sides of the line through :

Both conditions are needed. One alone is not enough:

 (a) proper crossing          (b) only one pair straddles           (c) collinear, overlapping
                                                     p4
     p3       p2                                    /               p1-----p3=====p2-----p4
       \     /                                     /
        \   /                 p1-----------p2  - -/- - - (line p1p2)
         \ /                                     /                  (d) collinear, disjoint
          X                                     p3
         / \                                                        p1-----p2    p3-----p4
        /   \
      p1     p4

 d1*d2 < 0 and d3*d4 < 0      d3*d4 < 0, but d1*d2 > 0:            all four orientations are 0:
 -> intersect                 p1, p2 on the same side of p3p4      decide by "endpoint on segment"
                              -> disjoint

In (b), and lie on opposite sides of the line through , but and are both on the same side of the line through : the two lines meet beyond , off the first segment. The segments miss.

Touching and collinear cases. If any orientation is zero, some endpoint lies on the other segment's line. Then the segments intersect exactly when some endpoint lies on the other segment. "On the segment" means: collinear with it (orientation 0) and inside its bounding box (between the endpoints in both and ). That single rule covers:

  • a T-junction (an endpoint touching the middle of the other segment),
  • two segments sharing an endpoint,
  • collinear overlapping segments (case c: lies on ),
  • and rejects collinear disjoint segments (case d: no endpoint lies on the other segment).

Why is checking endpoints enough in the collinear case? If two collinear segments overlap, their overlap is itself a segment whose two ends are endpoints of the originals, so at least one endpoint of one segment lies in the other.

flowchart TD
    S["Segments p1p2 and p3p4"] --> O["Compute d1, d2 (p1, p2 vs line p3p4) and d3, d4 (p3, p4 vs line p1p2)"]
    O --> Q{"d1*d2 < 0 and d3*d4 < 0?"}
    Q -->|"yes"| Y["Proper crossing: intersect"]
    Q -->|"no"| E{"Any endpoint lies on the other segment?<br/>(orient = 0 and inside bounding box)"}
    E -->|"yes"| T["Touch or overlap: intersect"]
    E -->|"no"| N["Disjoint"]

Trace. Six test pairs, computed by the code below ( left, right, collinear):

vs Proper?Endpoint on other?Result
vs yes—intersect at (case a)
vs nonodisjoint (case b)
vs nonodisjoint (neither straddles)
vs no on bothintersect (shared endpoint)
vs no on firstintersect (case c)
vs nononedisjoint (case d)

Where they cross. If you need the intersection point of two properly crossing segments, solve :

The denominator is zero exactly when the segments are parallel. On integer input, is a rational number: keep numerator and denominator as integers if later decisions depend on , or convert to floating point only for output.

2. Polygon area: the shoelace formula

A simple polygon is a closed chain of segments that does not cross itself, given as its vertices in order around the boundary. Its signed area is

Each term is , the cross product of two consecutive vertices seen as vectors from the origin: twice the signed area of the triangle (origin, , ). Adding these triangles around the polygon, the parts outside the polygon cancel (they are added once going one way and subtracted once coming back), and what remains is the polygon. The name comes from writing the coordinates in two columns and multiplying diagonally, crossing like shoelaces.

  • : the vertices are listed counter-clockwise.
  • : clockwise. The area is .
  • So the sign of the shoelace sum is also an orientation test for a whole polygon. Many algorithms (and file formats; see below) require a particular orientation, and this is how you check and fix it (reverse the list).

Trace on the pentagon :

TermRunning sum
0
1
2
3
4

Twice the signed area is , so the area is , and the order is counter-clockwise. Listing the same vertices in reverse gives . Notice a negative term (rows 0 and 4) is normal: those triangles from the origin are subtracted. Keep the sum as an integer ("twice the area") and divide by 2 only for output; that avoids fractions entirely.

The formula is for simple polygons. For a self-intersecting "bow-tie", the lobes have opposite orientations and their areas cancel; the result is the sum of each region times its winding number, which is rarely what you want.

3. Point in polygon

Given a simple polygon and a point , is inside, outside, or on the boundary?

Ray casting (even–odd rule). Shoot a ray from to the right (towards ) and count how many polygon edges it crosses. Odd: inside. Even: outside. This is the Jordan curve theorem in action: a simple closed curve splits the plane into an inside and an outside, and every crossing toggles between them.

   (0,5) +-----+       +-----+ (6,5)
         |     |       |     |
         | p o-|-------|-----|---->    p = (1,4): the ray crosses 3 edges -> inside
         |     |   q o-|-----|---->    q = (3,3): the ray crosses 2 edges -> outside (in the notch)
         |     +-------+     |
         |   (2,2)   (4,2)   |
         |                   |
   (0,0) +-------------------+ (6,0)

The idea is one sentence; the edge cases are the whole job:

  1. The ray passes exactly through a vertex. Counting both edges that meet there would count 2 when the boundary passes through the ray's line (should be 1), and counting neither would count 0 when the boundary only touches it (should be 0 or 2). The standard fix is the half-open rule: an edge counts only if one endpoint is strictly above 's horizontal line and the other is on or below it. In code: (a.y > p.y) != (b.y > p.y). A vertex on the line is treated as "below", consistently for both edges that share it. If the boundary passes through, exactly one of the two edges counts; if it touches and turns back, both or neither count. Both give the right parity.
  2. The ray runs along a horizontal edge. A horizontal edge has both endpoints at the same height, so the half-open test never counts it. Its two neighbouring edges decide, by rule 1.
  3. is on the boundary. Ray casting alone gives an arbitrary answer here. Check first: if lies on any edge (orientation 0 and inside the bounding box), report "boundary". Whether boundary counts as inside is the problem's choice, so return three values and let the caller decide.
  4. Is the crossing to the right of ? Do not compute the crossing's coordinate with a division. For an upward edge (with ), the crossing is to the right of exactly when is to the left of the edge: cross(a, b, p) > 0. For a downward edge, the signs flip. Combined: (cross(a, b, p) > 0) == (b.y > a.y). Exact on integers.

Trace on the U-shaped polygon , , , , , , , (a box with a notch cut from the top, between and , down to ):

PointWhat happensAnswer
edges crossed to the right: , , . Threeinside
in the notch: and . Twooutside
lies on the edge : caught by the boundary check before any countingboundary
the ray starts to the right of the notch; only is crossed. Oneinside
the ray runs through the corners and and along the notch's floor. Half-open rule: the floor is horizontal and never counts; counts (one end above, the other "on", which counts as below); likewise; and count. Fouroutside

Winding number. The winding number of a closed curve around is how many times the curve goes counter-clockwise around (clockwise turns count negative). Compute it with the same ray: each edge that crosses the ray upwards with on its left adds ; each edge crossing downwards with on its right adds . For a simple polygon the winding number is inside (the sign is the polygon's orientation) and outside, so it agrees with even–odd. They differ on self-intersecting polygons: in a star drawn with one stroke (a pentagram), the central pentagon has winding number 2. Even–odd calls it outside (a hole), the non-zero rule (winding ) calls it inside. SVG and the HTML canvas expose both as fill-rule: evenodd and fill-rule: nonzero; nonzero is the default in both.

Both methods are per query. For a convex polygon you can do : binary search for the "wedge" from vertex 0 that contains , then one orientation test against the far edge. For many queries against a fixed set of polygons, use a spatial index first (Spatial Trees).

4. Convex hull

A set is convex if the segment between any two of its points stays inside it. The convex hull of a finite point set is the smallest convex polygon containing all the points: stretch a rubber band around nails at the points and let go. Its corners, the hull vertices, are input points; the other points are inside or on its edges.

The hull answers "which points are extreme?", and it is the first step of many other algorithms: the farthest pair is a pair of hull vertices, the smallest enclosing rectangle has a side along a hull edge, and collision tests between convex shapes are much simpler than between arbitrary ones.

Output conventions (decide them up front; most hull bugs are convention bugs):

  • Vertices in counter-clockwise order, each once (the first is not repeated at the end).
  • Strict hull: points lying in the middle of a hull edge are not vertices. (Some problems, such as LeetCode's "Erect the Fence", want them included; see Collinear points.)
  • Duplicates removed first.
  • Degenerate inputs: one distinct point gives a 1-vertex hull; all points collinear gives the 2 extreme points.

Graham scan

Graham's 1972 algorithm:

  1. Pick the pivot: the lowest point (smallest , ties by smallest ). It is surely a hull vertex.
  2. Sort the other points by the angle they make with the pivot, counter-clockwise. Do this with the cross product as the comparator, not with atan2: comes before if cross(pivot, a, b) > 0. All points lie in the upper half-plane relative to the pivot, so this comparison is a consistent order. Points in the same direction are ordered by distance.
  3. Walk the sorted points, keeping a stack of the hull so far. Before pushing a point , pop the top while the last two stack points and do not make a left turn (cross <= 0). Then push .

The popping is the heart of it: if turns right (or goes straight), the top point is inside the triangle (pivot, second, ) or on its edge, so it cannot be a corner.

from functools import cmp_to_key


def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def graham_scan(points):
    """Graham scan. Strictly convex hull, counter-clockwise, starting at the lowest point."""
    pts = list(set(points))
    if len(pts) <= 2:
        return sorted(pts)
    pivot = min(pts, key=lambda p: (p[1], p[0]))        # lowest, then leftmost: surely on the hull
    rest = [p for p in pts if p != pivot]

    def by_angle(a, b):
        c = cross(pivot, a, b)
        if c != 0:
            return -1 if c > 0 else 1                     # a first if b lies to the left of pivot->a
        da = (a[0] - pivot[0]) ** 2 + (a[1] - pivot[1]) ** 2
        db = (b[0] - pivot[0]) ** 2 + (b[1] - pivot[1]) ** 2
        return -1 if da < db else 1                       # same direction: nearer first

    rest.sort(key=cmp_to_key(by_angle))                   # exact angular sort, no atan2
    stack = [pivot]
    for p in rest:
        while len(stack) >= 2 and cross(stack[-2], stack[-1], p) <= 0:
            stack.pop()                                   # not a left turn: stack top is not a corner
        stack.append(p)
    return stack


pts = [(0, 2), (2, 0), (3, 3), (4, 0), (4, 6), (5, 2), (7, 5), (8, 0), (10, 3)]
assert graham_scan(pts) == [(2, 0), (8, 0), (10, 3), (7, 5), (4, 6), (0, 2)]
assert graham_scan([(0, 0), (1, 1), (2, 2), (3, 3)]) == [(0, 0), (3, 3)]   # all collinear

Graham scan is elegant but its angular sort is fiddly: the comparator is only valid because every point is above the pivot, and ties (several points in the same direction) need care. Andrew's version avoids angles altogether.

Andrew's monotone chain

A. M. Andrew (1979) sorted the points by (ties by ) instead of by angle. The leftmost and rightmost points are on the hull, and they split it into two chains:

  • the lower hull, walking left to right along the bottom: every turn is a left turn;
  • the upper hull, walking right to left along the top: every turn is also a left turn.

Build each chain with the same stack loop as Graham: for each point in order, pop while the top two and the new point do not turn left, then push. Run it left to right for the lower hull, right to left for the upper hull, and glue them together (dropping the last point of each, because it is the first point of the other).

flowchart LR
    IN["Points"] --> SORT["Sort by x, then y, drop duplicates"]
    SORT --> LOW["Lower chain: scan left to right, pop while not a left turn"]
    SORT --> UP["Upper chain: scan right to left, pop while not a left turn"]
    LOW --> JOIN["lower minus last + upper minus last"]
    UP --> JOIN
    JOIN --> OUT["Hull, counter-clockwise, from the leftmost point"]

Trace. Nine points, sorted: A, B, C, D, E, F, G, H, I. Note that B, D, H all lie on , and that E, C, B happen to lie on one line (): both collinear cases appear. Each row is one orientation test cross(second, top, new).

ChainNew pointTest (second, top, new)crossActionStack after
lowerA——pushA
lowerB——pushA B
lowerCA B C8left turn, pushA B C
lowerDB C D−6right turn, pop CA B
lowerDA B D4left, pushA B D
lowerEB D E12left, pushA B D E
lowerFD E F−6right, pop EA B D
lowerFB D F4left, pushA B D F
lowerGD F G−1right, pop FA B D
lowerGB D G10left, pushA B D G
lowerHD G H−20right, pop GA B D
lowerHB D H0collinear, pop DA B
lowerHA B H12left, pushA B H
lowerIB H I18left, pushA B H I
upperI——pushI
upperH——pushI H
upperGI H G−13right, pop HI
upperG——pushI G
upperFI G F13left, pushI G F
upperEG F E−11right, pop FI G
upperEI G E3left, pushI G E
upperDG E D18left, pushI G E D
upperCE D C−6right, pop DI G E
upperCG E C10left, pushI G E C
upperBE C B0collinear, pop CI G E
upperBG E B20left, pushI G E B
upperAE B A−16right, pop BI G E
upperAG E A16left, pushI G E A

Lower chain A B H I, upper chain I G E A. Dropping each chain's last point and concatenating: A B H I G E, counter-clockwise from the leftmost point. C, D and F are discarded; D was popped because it lies in the middle of the bottom edge B–H (), and C because it lies in the middle of the line E–B, which at that moment was a candidate upper edge. Interior points (C, F) can be pushed and popped several times; that is fine, and the next section shows it costs only in total.

Step through the same run below. Green edges are the current chains, dashed grey edges were popped, amber nodes are the three points of the current test.

Collinear points: keep or drop

The pop condition decides what happens to points in the middle of a hull edge:

  • cross <= 0 (pop on right turns and straight lines): collinear points are dropped. The hull is strictly convex: every vertex is a real corner. This is the default here and in most libraries.
  • cross < 0 (pop only on right turns): collinear boundary points are kept. This is what "Erect the Fence" (LeetCode 587) wants. One extra trap: if all points are collinear, the lower and upper chains are the same points in opposite orders, and gluing them lists the middle points twice. Remove duplicates from the result (the practice ladder solution does).

Graham scan with < 0 needs one more fix: the points collinear with the pivot along the last direction must be visited farthest-first, otherwise the nearer ones get skipped. Andrew's version has no such special case, which is one reason it is the usual choice in contests.

5. Rotating calipers: the farthest pair

The diameter of a point set is the largest distance between two of its points. Brute force checks all pairs. Better: the farthest pair is always a pair of hull vertices (if one of them were inside, you could move it outward and get farther), so compute the hull first and then look only at pairs of hull vertices.

Michael Shamos (1978) showed that the farthest pair is an antipodal pair: two hull vertices that admit two parallel lines of support (lines touching the hull at those vertices, with the whole hull between them). Picture the hull clamped in a pair of calipers; rotate the calipers all the way around; the jaws touch only different vertex pairs, and the farthest pair is among them. Godfried Toussaint (1983) named the technique rotating calipers and showed that it solves a family of problems this way: diameter, width (smallest distance between parallel supporting lines), minimum-area and minimum-perimeter enclosing rectangles, and distances between two convex polygons.

The code form uses areas instead of angles. For each hull edge , the vertex farthest from the line through the edge is the one maximising cross(a, b, v) (twice the triangle area, i.e. the edge length times the distance). As the edge advances counter-clockwise, that farthest vertex also advances counter-clockwise, never backwards, so a single pointer goes around once. At each step, the pairs and are antipodal candidates.

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def dist_sq(p, q):
    return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2


def diameter_sq(hull):
    """Rotating calipers. hull: strictly convex, counter-clockwise. Returns the max squared distance."""
    h = len(hull)
    if h == 1:
        return 0
    if h == 2:
        return dist_sq(hull[0], hull[1])
    best, j = 0, 1
    for i in range(h):
        a, b = hull[i], hull[(i + 1) % h]
        # move j forward while the next vertex is farther from the line through edge a-b
        while cross(a, b, hull[(j + 1) % h]) > cross(a, b, hull[j]):
            j = (j + 1) % h
        best = max(best, dist_sq(a, hull[j]), dist_sq(b, hull[j]))
    return best


hull = [(0, 2), (2, 0), (8, 0), (10, 3), (7, 5), (4, 6)]
assert diameter_sq(hull) == 101                       # A(0,2) to I(10,3): sqrt(101) = 10.05
assert diameter_sq(hull) == max(dist_sq(p, q) for p in hull for q in hull)

Trace on the hull A B H I G E from the previous section:

EdgePointer movesFarthest vertex cross (2 × area)Candidates (squared distance)Best so far
A–BB → H → II22A–I 101, B–I 73101
B–HI → G → EE36B–E 40, H–E 52101
H–IE → AA28H–A 68, I–A 101101
I–GA → BB25I–B 73, G–B 50101
G–E(stays)B20G–B 50, E–B 40101
E–AB → HH40E–H 52, A–H 68101

The diameter is , between A and I, matching the brute-force maximum over all 36 pairs of the original nine points. The pointer advanced only 7 times over the 6 edges: the whole sweep is after the hull's .

6. Closest pair of points (pointer)

The opposite question, the closest pair, does not reduce to the hull (the closest two points are usually both interior). It has two classic solutions:

  • Divide and conquer (Shamos and Hoey, 1975): split by a vertical line, solve both halves, then check a narrow strip around the line, where a packing argument limits each point to a constant number of comparisons. The full algorithm, trace, proof of the "at most 7 comparisons" bound and code in four languages are in Divide & Conquer: closest pair of points.
  • Sweep line: process points by increasing , keep the points within the current best distance of the sweep line in a balanced BST ordered by , and for each new point look only at BST entries with within . Same bound, often shorter code (a std::set in C++). CSES "Minimum Euclidean Distance" in the practice ladder is exactly this.

Use squared distances throughout so everything stays an integer.

7. Sweep line

A sweep line algorithm imagines a vertical line moving left to right across the plane, stopping only at events (points where something changes: a segment starts, a segment ends, two segments cross). It keeps a status structure describing what the line currently cuts, and does work only at events. The plane is 2-D, but the sweep reduces it to a sequence of 1-D problems. This is the geometric twin of the "sort the events, then scan" technique in Intervals.

Do any two of segments intersect? (Shamos–Hoey, 1976). Brute force tests all pairs: . The sweep does it in :

  1. Events: every segment's left endpoint (insert) and right endpoint (delete), sorted by .
  2. Status: the segments currently cut by the sweep line, ordered by the where they cross the line, in a balanced BST.
  3. On insert, compare the new segment with its neighbours just above and below in the status. On delete, compare the two segments that become neighbours. If any comparison finds an intersection, stop.
flowchart LR
    EV["Endpoints sorted by x"] --> NEXT{"Next event"}
    NEXT -->|"left endpoint"| INS["Insert segment into status by y<br/>test it vs new neighbours above and below"]
    NEXT -->|"right endpoint"| DEL["Remove segment<br/>test the two segments that become neighbours"]
    INS --> HIT{"Intersection found?"}
    DEL --> HIT
    HIT -->|"yes"| YES["Report: some pair intersects"]
    HIT -->|"no"| NEXT

Why are neighbours enough? Suppose and cross, and take the leftmost crossing point among all crossing pairs. Just before (and after any events left of it), nothing lies between and on the sweep line, because anything between them would have to cross one of them before . So and become neighbours at some event at or before , and the algorithm tests them then. The status order never becomes inconsistent before the first crossing, which is why stopping at the first one makes the BST valid.

Report all crossings (Bentley–Ottmann, 1979). Do not stop: also schedule each discovered crossing as a future event, and at that event swap the two segments in the status (they change order there) and test each against its new neighbour. Time , which beats when crossings are few. Degenerate inputs (vertical segments, three segments through one point, overlapping segments) are the hard part of implementing it; de Berg et al., chapter 2, handle them carefully.

Area of a union of rectangles. "How much ground do these axis-aligned rectangles cover?" Sweep a vertical line over the rectangles' left and right edges. Between two consecutive events, the covered length of the sweep line is constant, so the area there is that length times the gap in . Maintain a count of how many rectangles cover each elementary -interval (after coordinate compression: sort the distinct values). Recomputing the covered length naively is per event, total; a segment tree storing "cover count, covered length" per node makes it . This is Klee's measure problem in 2-D; Jon Bentley gave the sweep in 1977. LeetCode 850 in the practice ladder is exactly this.

8. Pick's theorem

For a simple polygon whose vertices are all lattice points (integer coordinates), Georg Pick (1899) proved

where is the area, the number of lattice points strictly inside, and the number on the boundary. The boundary count is easy: an edge from to passes through lattice points including both ends, so summing s over the edges counts each boundary point once (each vertex is the start of exactly one edge). With from the shoelace formula, solve for the interior: , or in integers, .

Verified example. The quadrilateral :

Edge
6, 06
2, 42
4, 22
0, 22

. Shoelace: , so . Pick: . Counting the lattice points one by one with the point-in-polygon code gives 11 inside and 12 on the boundary, as predicted. (The gcd of and is , so axis-parallel edges work too.) Pick's theorem needs integer vertices and a polygon without holes; for a polygon with holes, it becomes .

9. Half-plane intersection (mention)

A half-plane is everything on one side of a line, such as , or "everything to the left of the directed line ". The intersection of half-planes is a convex polygon (possibly empty or unbounded). It answers "where can the robot stand so that it sees all these walls?" (the kernel of a polygon), "what region satisfies these linear constraints?" (2-D linear programming is a special case; see Linear Programming), and "which points are closer to site than to every other site?" (one cell of a Voronoi diagram).

The standard algorithm sorts the half-planes by the angle of their boundary lines and sweeps them with a deque, popping from both ends while the last intersection point falls outside the new half-plane: the same "pop while not a left turn" idea as the hull, run on lines instead of points (this is projective duality at work). cp-algorithms.com's "Half-plane intersection – S&I Algorithm in O(N log N)" has a careful implementation. Expect parallel lines and empty or unbounded results to be the hard cases, and add a large bounding box to make the result bounded.

The ladder: brute force → better → optimal

The problem: the convex hull of points.

Rung 1 — brute force over edges, . A pair is a hull edge exactly when all other points lie on one side of the line (on the left, for counter-clockwise order). Test each of the ordered pairs against all points. Correct and easy to write; good as a test oracle. (Even slower, : a point is a hull vertex unless it lies in a triangle of three other points. The random tests in the implementation use this one, because it shares no logic with the fast algorithms.)

Rung 2 — gift wrapping (Jarvis march, 1973), . Start at the leftmost point. Repeatedly pick the next hull vertex as the point such that every other point is to the left of : one pass per hull vertex, vertices. Better because each step finds a whole hull edge in one pass instead of testing every pair. Excellent when is tiny (random points in a disc have hulls of about vertices; in a square, ); quadratic when every point is on the hull (points on a circle).

Rung 3 — Graham scan or monotone chain, . Sort once, then one linear stack pass. The sort dominates. Each point is pushed once and popped at most once per chain, so the scan is .

Is optimal? Yes, in the algebraic decision-tree model: sorting reduces to it. Given numbers , place the points on a parabola. All of them are hull vertices, and the hull in counter-clockwise order lists them sorted by . So a hull algorithm faster than would sort faster than the sorting lower bound (Sorting in the Real World discusses that bound). (Yao, 1981, proved the stronger statement that even identifying the hull vertices needs in this model.)

Output-sensitive optimum — Chan's algorithm (1996), . Split the points into groups of size , compute each group's hull with Graham scan, then run gift wrapping where each step finds the best next point in each small hull by binary search. Guess for until . Kirkpatrick and Seidel had reached in 1986 with a more complex "marriage-before-conquest" method. These matter in theory and for huge inputs with tiny hulls; in practice, monotone chain (often after discarding the points inside the quadrilateral of the four extreme points, the Akl–Toussaint heuristic) is what people ship.

RungAlgorithmTimeSpaceBetter becauseUse when
1All pairs, test all points—Test oracle,
2Gift wrapping (Jarvis) extraone pass per hull edgevery few hull vertices
3Graham scansort once, amortised linear scanclassic, polar order needed
3Monotone chain (Andrew)no angles, simplest degenerate handlingdefault choice
—Chan / Kirkpatrick–Seideloutput-sensitivetheory, huge with small

Correctness

The orientation test. , where is the counter-clockwise angle from to . Lengths are positive, so the sign is the sign of : positive for (left), negative for (right), zero for or (collinear). On integer input every operation is exact, so the computed sign is the true sign.

Segment intersection. If the segments properly cross at , then is strictly between and on the line , and the line passes through without containing , so and are strictly on opposite sides of it (); symmetrically . Conversely, if , the segment crosses the line at exactly one point, and puts that point strictly between and (by the same argument on the other line), so it is on both segments. Every intersection that is not proper involves an endpoint lying on the other segment, which the second check tests directly, and in the collinear case the overlap argument above shows that checking endpoints suffices.

Shoelace. Induction on triangles: for a triangle , expanding gives exactly the three shoelace terms, and that cross product is twice the signed area. A simple polygon with vertices has a diagonal (the "two ears" theorem), which splits it into two simple polygons whose shoelace sums add up to the original's: the diagonal's two terms appear once in each direction and cancel. Alternatively, it is Green's theorem evaluated on straight edges.

Ray casting. By the Jordan curve theorem, a ray from to infinity ends outside, and each proper crossing of the boundary switches between inside and outside, so the parity of crossings is the answer. The half-open rule turns non-proper situations into the correct count: perturb the ray infinitesimally upwards; then it never touches a vertex, and "edge has one endpoint strictly above and the other at or below" is exactly "edge crosses the perturbed ray's line".

Monotone chain. Claim: after processing points (in sorted order), the lower stack is exactly the lower hull of , strictly convex. Base: one or two points are their own lower hull. Step: add , which has the largest so far, so it is on the lower hull of the new set. A stack vertex remains on the lower hull iff the polyline still turns left at . Popping removes exactly the vertices at which the turn toward is not left; once the top two and make a left turn, all earlier turns were already left (the inductive hypothesis) and stay left (they do not involve ), and by convexity of the old chain no earlier vertex can be "under" the new edge. So the invariant holds. The upper chain is symmetric. Gluing: both chains start and end at the leftmost and rightmost points, which are therefore the only vertices shared.

Amortised linear scan. Each point is pushed once per chain and can be popped at most once per chain, so the total number of pops is at most ; the while loop's total work over the whole scan is , even though a single step can pop many points. This is the same potential argument as for monotonic stacks.

Rotating calipers. For a strictly convex polygon and a fixed edge, the distance to the edge's line, as you go around the vertices, increases and then decreases (it is unimodal), so the while loop stops at the farthest vertex. As the edge rotates counter-clockwise, the direction perpendicular to it also rotates counter-clockwise, so the farthest vertex never moves backwards: the pointer goes around at most once more than the edge loop. Every antipodal pair occurs as (endpoint of some edge, farthest vertex from that edge), and the farthest pair is antipodal (Shamos), so the maximum is found.

Complexity

OperationTimeSpaceNotes
Orientation, segment intersection test64-bit exact for
Shoelace areakeep twice the area as an integer
Point in polygon (ray casting, winding) per query per query for convex polygons
Convex hull (monotone chain, Graham) if the points are already sorted
Gift wrappingoutput-sensitive
Rotating calipers (after the hull)diameter, width, enclosing rectangle
Closest pairD&C or sweep
Any segments intersect (Shamos–Hoey)balanced BST status
All intersections (Bentley–Ottmann) space with care
Union of rectangles areasweep + segment tree; naive sweep
Half-plane intersectionsort by angle + deque

Best, average and worst cases coincide for the hull algorithms except gift wrapping, whose cost depends on . Space for hulls is the sorted copy plus the stack.

Implementation

All four snippets implement the same toolkit on integer points: cross/orient, onSegment, segmentsIntersect, twiceSignedArea (shoelace), pointInPolygon (ray casting; returns 1 inside, 0 boundary, −1 outside), windingNumber, and convexHull (monotone chain, strict, counter-clockwise). Each main checks the worked examples from this page and then runs 400 random tests on small integer grids (lots of duplicates and collinear points), checking the hull against a brute-force oracle: the hull must be strictly convex and counter-clockwise, every input point must be inside or on it, and its vertex set must equal the set of points that lie in no triangle (or segment) of other points.

"""Computational geometry toolkit on integer points: orientation, segment intersection,
shoelace area, point in polygon (ray casting + winding number), monotone chain hull."""
import random


def cross(o, a, b):
    """z-component of (a - o) x (b - o): > 0 left turn (CCW), < 0 right turn, 0 collinear."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def orient(o, a, b):
    c = cross(o, a, b)
    return (c > 0) - (c < 0)


def on_segment(p, a, b):
    """p lies on the closed segment ab (p must be collinear with a and b)."""
    return (orient(a, b, p) == 0
            and min(a[0], b[0]) <= p[0] <= max(a[0], b[0])
            and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]))


def segments_intersect(p1, p2, p3, p4):
    """Do closed segments p1p2 and p3p4 share at least one point?"""
    d1, d2 = orient(p3, p4, p1), orient(p3, p4, p2)
    d3, d4 = orient(p1, p2, p3), orient(p1, p2, p4)
    if d1 * d2 < 0 and d3 * d4 < 0:
        return True                        # proper crossing
    return (on_segment(p1, p3, p4) or on_segment(p2, p3, p4)
            or on_segment(p3, p1, p2) or on_segment(p4, p1, p2))


def twice_signed_area(poly):
    """Shoelace: 2 * signed area. Positive = counter-clockwise vertex order."""
    s = 0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return s


def point_in_polygon(p, poly):
    """Ray casting to +x. Returns 1 inside, 0 on the boundary, -1 outside."""
    inside = False
    n = len(poly)
    for i in range(n):
        a, b = poly[i], poly[(i + 1) % n]
        if on_segment(p, a, b):
            return 0
        if (a[1] > p[1]) != (b[1] > p[1]):          # edge straddles the ray's line (half-open rule)
            # crossing is to the right of p  <=>  orientation test, no division
            if (cross(a, b, p) > 0) == (b[1] > a[1]):
                inside = not inside
    return 1 if inside else -1


def winding_number(p, poly):
    """How many times poly winds counter-clockwise around p (p not on the boundary)."""
    w = 0
    n = len(poly)
    for i in range(n):
        a, b = poly[i], poly[(i + 1) % n]
        if a[1] <= p[1] < b[1] and cross(a, b, p) > 0:
            w += 1                                   # upward edge, p strictly left
        elif b[1] <= p[1] < a[1] and cross(a, b, p) < 0:
            w -= 1                                   # downward edge, p strictly right
    return w


def convex_hull(points):
    """Andrew's monotone chain. Strictly convex hull, counter-clockwise, no repeated first vertex."""
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]


# ---------------------------------------------------------------- brute-force checks
def is_extreme(p, others):
    """p is a hull vertex iff it is not inside a (possibly flat) triangle of other points."""
    m = len(others)
    for i in range(m):
        for j in range(i + 1, m):
            if on_segment(p, others[i], others[j]):
                return False
            for k in range(j + 1, m):
                a, b, c = others[i], others[j], others[k]
                s1, s2, s3 = orient(a, b, p), orient(b, c, p), orient(c, a, p)
                if orient(a, b, c) != 0 and (min(s1, s2, s3) >= 0 or max(s1, s2, s3) <= 0):
                    return False
    return True


def check_hull(points, hull):
    pts = sorted(set(points))
    h = len(hull)
    if h >= 3:
        for i in range(h):                        # strictly convex, counter-clockwise
            assert cross(hull[i], hull[(i + 1) % h], hull[(i + 2) % h]) > 0
        for p in pts:                             # every point inside or on the hull
            assert all(cross(hull[i], hull[(i + 1) % h], p) >= 0 for i in range(h))
    extreme = [p for p in pts if is_extreme(p, [q for q in pts if q != p])]
    assert sorted(hull) == sorted(extreme), (points, hull, extreme)


def main():
    # orientation and segments
    assert orient((0, 0), (4, 0), (2, 3)) == 1 and orient((0, 0), (4, 0), (2, -1)) == -1
    assert segments_intersect((0, 0), (4, 4), (0, 4), (4, 0))          # X shape
    assert not segments_intersect((0, 0), (2, 2), (3, 3), (5, 5))      # collinear, disjoint
    assert segments_intersect((0, 0), (3, 3), (2, 2), (5, 5))          # collinear, overlapping
    assert segments_intersect((0, 0), (2, 0), (2, 0), (2, 5))          # touch at an endpoint
    assert not segments_intersect((0, 0), (4, 0), (1, 1), (3, 2))
    assert not segments_intersect((0, 0), (4, 0), (5, -1), (6, 1))     # only one pair straddles
    # shoelace
    poly = [(1, 1), (5, 0), (6, 4), (3, 6), (0, 4)]
    assert twice_signed_area(poly) == 47                               # area 23.5, CCW
    assert twice_signed_area(poly[::-1]) == -47                        # clockwise: negative
    # point in polygon on a concave "U" shape
    u = [(0, 0), (6, 0), (6, 5), (4, 5), (4, 2), (2, 2), (2, 5), (0, 5)]
    assert point_in_polygon((1, 4), u) == 1
    assert point_in_polygon((3, 4), u) == -1       # inside the notch
    assert point_in_polygon((3, 2), u) == 0        # on an edge
    assert point_in_polygon((5, 2), u) == 1        # ray passes through vertex (4,2) and (6,..)
    assert point_in_polygon((-1, 2), u) == -1      # ray runs along the edge y = 2
    assert winding_number((1, 4), u) == 1 and winding_number((3, 4), u) == 0
    # hull
    pts = [(0, 0), (4, 0), (2, 0), (4, 4), (0, 4), (2, 2), (1, 3), (4, 2)]
    assert convex_hull(pts) == [(0, 0), (4, 0), (4, 4), (0, 4)]
    # random tests against brute force
    rng = random.Random(8)
    for _ in range(400):
        n = rng.randint(1, 12)
        points = [(rng.randint(-4, 4), rng.randint(-4, 4)) for _ in range(n)]
        hull = convex_hull(points)
        check_hull(points, hull)
        if len(hull) >= 3:
            for _ in range(5):
                q = (rng.randint(-5, 5), rng.randint(-5, 5))
                inside_hull = all(cross(hull[i], hull[(i + 1) % len(hull)], q) >= 0 for i in range(len(hull)))
                assert (point_in_polygon(q, hull) >= 0) == inside_hull
    print("all geometry tests passed")


if __name__ == "__main__":
    main()
import java.util.*;

public class Main {
    record P(long x, long y) implements Comparable<P> {
        public int compareTo(P o) { return x != o.x ? Long.compare(x, o.x) : Long.compare(y, o.y); }
    }

    // z-component of (a - o) x (b - o): > 0 left turn (CCW), < 0 right turn, 0 collinear
    static long cross(P o, P a, P b) {
        return (a.x() - o.x()) * (b.y() - o.y()) - (a.y() - o.y()) * (b.x() - o.x());
    }

    static int orient(P o, P a, P b) { return Long.signum(cross(o, a, b)); }

    static boolean onSegment(P p, P a, P b) {
        return orient(a, b, p) == 0
            && Math.min(a.x(), b.x()) <= p.x() && p.x() <= Math.max(a.x(), b.x())
            && Math.min(a.y(), b.y()) <= p.y() && p.y() <= Math.max(a.y(), b.y());
    }

    static boolean segmentsIntersect(P p1, P p2, P p3, P p4) {
        int d1 = orient(p3, p4, p1), d2 = orient(p3, p4, p2);
        int d3 = orient(p1, p2, p3), d4 = orient(p1, p2, p4);
        if (d1 * d2 < 0 && d3 * d4 < 0) return true;           // proper crossing
        return onSegment(p1, p3, p4) || onSegment(p2, p3, p4)
            || onSegment(p3, p1, p2) || onSegment(p4, p1, p2);
    }

    // Shoelace: 2 * signed area, positive for counter-clockwise order
    static long twiceSignedArea(List<P> poly) {
        long s = 0;
        int n = poly.size();
        for (int i = 0; i < n; i++) {
            P a = poly.get(i), b = poly.get((i + 1) % n);
            s += a.x() * b.y() - b.x() * a.y();
        }
        return s;
    }

    // Ray casting to +x: 1 inside, 0 on the boundary, -1 outside
    static int pointInPolygon(P p, List<P> poly) {
        boolean inside = false;
        int n = poly.size();
        for (int i = 0; i < n; i++) {
            P a = poly.get(i), b = poly.get((i + 1) % n);
            if (onSegment(p, a, b)) return 0;
            if ((a.y() > p.y()) != (b.y() > p.y())) {           // half-open straddle rule
                if ((cross(a, b, p) > 0) == (b.y() > a.y())) inside = !inside;
            }
        }
        return inside ? 1 : -1;
    }

    static int windingNumber(P p, List<P> poly) {
        int w = 0, n = poly.size();
        for (int i = 0; i < n; i++) {
            P a = poly.get(i), b = poly.get((i + 1) % n);
            if (a.y() <= p.y() && p.y() < b.y() && cross(a, b, p) > 0) w++;
            else if (b.y() <= p.y() && p.y() < a.y() && cross(a, b, p) < 0) w--;
        }
        return w;
    }

    // Andrew's monotone chain: strictly convex hull, counter-clockwise
    static List<P> convexHull(List<P> points) {
        List<P> pts = new ArrayList<>(new TreeSet<>(points));
        int n = pts.size();
        if (n <= 2) return pts;
        P[] h = new P[2 * n];
        int k = 0;
        for (P p : pts) {                                       // lower chain
            while (k >= 2 && cross(h[k - 2], h[k - 1], p) <= 0) k--;
            h[k++] = p;
        }
        for (int i = n - 2, t = k + 1; i >= 0; i--) {           // upper chain
            P p = pts.get(i);
            while (k >= t && cross(h[k - 2], h[k - 1], p) <= 0) k--;
            h[k++] = p;
        }
        return new ArrayList<>(Arrays.asList(h).subList(0, k - 1));
    }

    // brute force: p is a hull vertex iff it lies in no (possibly flat) triangle of other points
    static boolean isExtreme(P p, List<P> o) {
        int m = o.size();
        for (int i = 0; i < m; i++)
            for (int j = i + 1; j < m; j++) {
                if (onSegment(p, o.get(i), o.get(j))) return false;
                for (int k = j + 1; k < m; k++) {
                    P a = o.get(i), b = o.get(j), c = o.get(k);
                    if (orient(a, b, c) == 0) continue;
                    int s1 = orient(a, b, p), s2 = orient(b, c, p), s3 = orient(c, a, p);
                    if (Math.min(s1, Math.min(s2, s3)) >= 0 || Math.max(s1, Math.max(s2, s3)) <= 0) return false;
                }
            }
        return true;
    }

    static List<P> poly(long... c) {
        List<P> r = new ArrayList<>();
        for (int i = 0; i < c.length; i += 2) r.add(new P(c[i], c[i + 1]));
        return r;
    }

    static void check(boolean ok) { if (!ok) throw new AssertionError(); }

    public static void main(String[] args) {
        check(orient(new P(0, 0), new P(4, 0), new P(2, 3)) == 1);
        check(segmentsIntersect(new P(0, 0), new P(4, 4), new P(0, 4), new P(4, 0)));
        check(!segmentsIntersect(new P(0, 0), new P(2, 2), new P(3, 3), new P(5, 5)));
        check(segmentsIntersect(new P(0, 0), new P(3, 3), new P(2, 2), new P(5, 5)));
        check(segmentsIntersect(new P(0, 0), new P(2, 0), new P(2, 0), new P(2, 5)));
        check(!segmentsIntersect(new P(0, 0), new P(4, 0), new P(1, 1), new P(3, 2)));
        check(twiceSignedArea(poly(1, 1, 5, 0, 6, 4, 3, 6, 0, 4)) == 47);       // area 23.5
        List<P> u = poly(0, 0, 6, 0, 6, 5, 4, 5, 4, 2, 2, 2, 2, 5, 0, 5);
        check(pointInPolygon(new P(1, 4), u) == 1 && pointInPolygon(new P(3, 4), u) == -1);
        check(pointInPolygon(new P(3, 2), u) == 0 && pointInPolygon(new P(5, 2), u) == 1);
        check(pointInPolygon(new P(-1, 2), u) == -1);
        check(windingNumber(new P(1, 4), u) == 1 && windingNumber(new P(3, 4), u) == 0);
        check(convexHull(poly(0, 0, 4, 0, 2, 0, 4, 4, 0, 4, 2, 2, 1, 3, 4, 2)).equals(poly(0, 0, 4, 0, 4, 4, 0, 4)));

        Random rng = new Random(8);
        for (int t = 0; t < 400; t++) {
            List<P> pts = new ArrayList<>();
            int n = 1 + rng.nextInt(12);
            for (int i = 0; i < n; i++) pts.add(new P(rng.nextInt(9) - 4, rng.nextInt(9) - 4));
            List<P> hull = convexHull(pts);
            int h = hull.size();
            if (h >= 3) {
                for (int i = 0; i < h; i++) check(cross(hull.get(i), hull.get((i + 1) % h), hull.get((i + 2) % h)) > 0);
                for (P p : pts) {
                    for (int i = 0; i < h; i++) check(cross(hull.get(i), hull.get((i + 1) % h), p) >= 0);
                    check(pointInPolygon(p, hull) >= 0);
                }
            }
            List<P> uniq = new ArrayList<>(new TreeSet<>(pts)), extreme = new ArrayList<>();
            for (P p : uniq) {
                List<P> others = new ArrayList<>(uniq);
                others.remove(p);
                if (isExtreme(p, others)) extreme.add(p);
            }
            List<P> sortedHull = new ArrayList<>(hull);
            Collections.sort(sortedHull);
            check(sortedHull.equals(extreme));
        }
        System.out.println("all geometry tests passed");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>

using ll = long long;
struct P {
    ll x, y;
    bool operator<(const P& o) const { return x != o.x ? x < o.x : y < o.y; }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};

// z-component of (a - o) x (b - o): > 0 left turn (CCW), < 0 right turn, 0 collinear
ll cross(const P& o, const P& a, const P& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int orient(const P& o, const P& a, const P& b) {
    ll c = cross(o, a, b);
    return (c > 0) - (c < 0);
}

bool onSegment(const P& p, const P& a, const P& b) {
    return orient(a, b, p) == 0 && std::min(a.x, b.x) <= p.x && p.x <= std::max(a.x, b.x) &&
           std::min(a.y, b.y) <= p.y && p.y <= std::max(a.y, b.y);
}

bool segmentsIntersect(const P& p1, const P& p2, const P& p3, const P& p4) {
    int d1 = orient(p3, p4, p1), d2 = orient(p3, p4, p2);
    int d3 = orient(p1, p2, p3), d4 = orient(p1, p2, p4);
    if (d1 * d2 < 0 && d3 * d4 < 0) return true;  // proper crossing
    return onSegment(p1, p3, p4) || onSegment(p2, p3, p4) || onSegment(p3, p1, p2) || onSegment(p4, p1, p2);
}

// Shoelace: 2 * signed area, positive for counter-clockwise order
ll twiceSignedArea(const std::vector<P>& poly) {
    ll s = 0;
    size_t n = poly.size();
    for (size_t i = 0; i < n; i++) {
        const P &a = poly[i], &b = poly[(i + 1) % n];
        s += a.x * b.y - b.x * a.y;
    }
    return s;
}

// Ray casting to +x: 1 inside, 0 on the boundary, -1 outside
int pointInPolygon(const P& p, const std::vector<P>& poly) {
    bool inside = false;
    size_t n = poly.size();
    for (size_t i = 0; i < n; i++) {
        const P &a = poly[i], &b = poly[(i + 1) % n];
        if (onSegment(p, a, b)) return 0;
        if ((a.y > p.y) != (b.y > p.y) && (cross(a, b, p) > 0) == (b.y > a.y)) inside = !inside;
    }
    return inside ? 1 : -1;
}

int windingNumber(const P& p, const std::vector<P>& poly) {
    int w = 0;
    size_t n = poly.size();
    for (size_t i = 0; i < n; i++) {
        const P &a = poly[i], &b = poly[(i + 1) % n];
        if (a.y <= p.y && p.y < b.y && cross(a, b, p) > 0) w++;
        else if (b.y <= p.y && p.y < a.y && cross(a, b, p) < 0) w--;
    }
    return w;
}

// Andrew's monotone chain: strictly convex hull, counter-clockwise
std::vector<P> convexHull(std::vector<P> pts) {
    std::sort(pts.begin(), pts.end());
    pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
    int n = (int)pts.size(), k = 0;
    if (n <= 2) return pts;
    std::vector<P> h(2 * n);
    for (int i = 0; i < n; i++) {  // lower chain
        while (k >= 2 && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
        h[k++] = pts[i];
    }
    for (int i = n - 2, t = k + 1; i >= 0; i--) {  // upper chain
        while (k >= t && cross(h[k - 2], h[k - 1], pts[i]) <= 0) k--;
        h[k++] = pts[i];
    }
    h.resize(k - 1);
    return h;
}

// brute force: p is a hull vertex iff it lies in no (possibly flat) triangle of other points
bool isExtreme(const P& p, const std::vector<P>& o) {
    size_t m = o.size();
    for (size_t i = 0; i < m; i++)
        for (size_t j = i + 1; j < m; j++) {
            if (onSegment(p, o[i], o[j])) return false;
            for (size_t k = j + 1; k < m; k++) {
                if (orient(o[i], o[j], o[k]) == 0) continue;
                int s1 = orient(o[i], o[j], p), s2 = orient(o[j], o[k], p), s3 = orient(o[k], o[i], p);
                if (std::min({s1, s2, s3}) >= 0 || std::max({s1, s2, s3}) <= 0) return false;
            }
        }
    return true;
}

int main() {
    assert(orient({0, 0}, {4, 0}, {2, 3}) == 1);
    assert(segmentsIntersect({0, 0}, {4, 4}, {0, 4}, {4, 0}));
    assert(!segmentsIntersect({0, 0}, {2, 2}, {3, 3}, {5, 5}));
    assert(segmentsIntersect({0, 0}, {3, 3}, {2, 2}, {5, 5}));
    assert(segmentsIntersect({0, 0}, {2, 0}, {2, 0}, {2, 5}));
    assert(!segmentsIntersect({0, 0}, {4, 0}, {1, 1}, {3, 2}));
    assert(twiceSignedArea({{1, 1}, {5, 0}, {6, 4}, {3, 6}, {0, 4}}) == 47);  // area 23.5
    std::vector<P> u = {{0, 0}, {6, 0}, {6, 5}, {4, 5}, {4, 2}, {2, 2}, {2, 5}, {0, 5}};
    assert(pointInPolygon({1, 4}, u) == 1 && pointInPolygon({3, 4}, u) == -1);
    assert(pointInPolygon({3, 2}, u) == 0 && pointInPolygon({5, 2}, u) == 1);
    assert(pointInPolygon({-1, 2}, u) == -1);
    assert(windingNumber({1, 4}, u) == 1 && windingNumber({3, 4}, u) == 0);
    std::vector<P> expect = {{0, 0}, {4, 0}, {4, 4}, {0, 4}};
    assert(convexHull({{0, 0}, {4, 0}, {2, 0}, {4, 4}, {0, 4}, {2, 2}, {1, 3}, {4, 2}}) == expect);

    std::mt19937 rng(8);
    for (int t = 0; t < 400; t++) {
        std::vector<P> pts;
        int n = 1 + (int)(rng() % 12);
        for (int i = 0; i < n; i++) pts.push_back({(ll)(rng() % 9) - 4, (ll)(rng() % 9) - 4});
        std::vector<P> hull = convexHull(pts);
        size_t h = hull.size();
        if (h >= 3) {
            for (size_t i = 0; i < h; i++) assert(cross(hull[i], hull[(i + 1) % h], hull[(i + 2) % h]) > 0);
            for (const P& p : pts) {
                for (size_t i = 0; i < h; i++) assert(cross(hull[i], hull[(i + 1) % h], p) >= 0);
                assert(pointInPolygon(p, hull) >= 0);
            }
        }
        std::vector<P> uniq = pts, extreme;
        std::sort(uniq.begin(), uniq.end());
        uniq.erase(std::unique(uniq.begin(), uniq.end()), uniq.end());
        for (const P& p : uniq) {
            std::vector<P> others;
            for (const P& q : uniq) if (!(q == p)) others.push_back(q);
            if (isExtreme(p, others)) extreme.push_back(p);
        }
        std::sort(hull.begin(), hull.end());
        assert(hull == extreme);
    }
    std::cout << "all geometry tests passed\n";
}
type P = [number, number];

// z-component of (a - o) x (b - o): > 0 left turn (CCW), < 0 right turn, 0 collinear.
// Exact while |coordinates| stay below about 4.7e7 (products must fit in 2^53).
function cross(o: P, a: P, b: P): number {
  return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]);
}
function orient(o: P, a: P, b: P): number {
  return Math.sign(cross(o, a, b));
}

function onSegment(p: P, a: P, b: P): boolean {
  return orient(a, b, p) === 0 &&
    Math.min(a[0], b[0]) <= p[0] && p[0] <= Math.max(a[0], b[0]) &&
    Math.min(a[1], b[1]) <= p[1] && p[1] <= Math.max(a[1], b[1]);
}

function segmentsIntersect(p1: P, p2: P, p3: P, p4: P): boolean {
  const d1 = orient(p3, p4, p1), d2 = orient(p3, p4, p2);
  const d3 = orient(p1, p2, p3), d4 = orient(p1, p2, p4);
  if (d1 * d2 < 0 && d3 * d4 < 0) return true; // proper crossing
  return onSegment(p1, p3, p4) || onSegment(p2, p3, p4) ||
    onSegment(p3, p1, p2) || onSegment(p4, p1, p2);
}

// Shoelace: 2 * signed area, positive for counter-clockwise order
function twiceSignedArea(poly: P[]): number {
  let s = 0;
  for (let i = 0; i < poly.length; i++) {
    const [x1, y1] = poly[i], [x2, y2] = poly[(i + 1) % poly.length];
    s += x1 * y2 - x2 * y1;
  }
  return s;
}

// Ray casting to +x: 1 inside, 0 on the boundary, -1 outside
function pointInPolygon(p: P, poly: P[]): number {
  let inside = false;
  for (let i = 0; i < poly.length; i++) {
    const a = poly[i], b = poly[(i + 1) % poly.length];
    if (onSegment(p, a, b)) return 0;
    if ((a[1] > p[1]) !== (b[1] > p[1]) && (cross(a, b, p) > 0) === (b[1] > a[1])) inside = !inside;
  }
  return inside ? 1 : -1;
}

function windingNumber(p: P, poly: P[]): number {
  let w = 0;
  for (let i = 0; i < poly.length; i++) {
    const a = poly[i], b = poly[(i + 1) % poly.length];
    if (a[1] <= p[1] && p[1] < b[1] && cross(a, b, p) > 0) w++;
    else if (b[1] <= p[1] && p[1] < a[1] && cross(a, b, p) < 0) w--;
  }
  return w;
}

const byXY = (a: P, b: P): number => a[0] - b[0] || a[1] - b[1];

// Andrew's monotone chain: strictly convex hull, counter-clockwise
function convexHull(points: P[]): P[] {
  const pts = [...points].sort(byXY).filter((p, i, arr) => i === 0 || byXY(p, arr[i - 1]) !== 0);
  if (pts.length <= 2) return pts;
  const lower: P[] = [], upper: P[] = [];
  for (const p of pts) {
    while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], p) <= 0) lower.pop();
    lower.push(p);
  }
  for (let i = pts.length - 1; i >= 0; i--) {
    const p = pts[i];
    while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], p) <= 0) upper.pop();
    upper.push(p);
  }
  return lower.slice(0, -1).concat(upper.slice(0, -1));
}

// brute force: p is a hull vertex iff it lies in no (possibly flat) triangle of other points
function isExtreme(p: P, o: P[]): boolean {
  for (let i = 0; i < o.length; i++)
    for (let j = i + 1; j < o.length; j++) {
      if (onSegment(p, o[i], o[j])) return false;
      for (let k = j + 1; k < o.length; k++) {
        if (orient(o[i], o[j], o[k]) === 0) continue;
        const s = [orient(o[i], o[j], p), orient(o[j], o[k], p), orient(o[k], o[i], p)];
        if (Math.min(...s) >= 0 || Math.max(...s) <= 0) return false;
      }
    }
  return true;
}

function assert(ok: boolean, msg = "assertion failed"): void {
  if (!ok) throw new Error(msg);
}

assert(orient([0, 0], [4, 0], [2, 3]) === 1);
assert(segmentsIntersect([0, 0], [4, 4], [0, 4], [4, 0]));
assert(!segmentsIntersect([0, 0], [2, 2], [3, 3], [5, 5]));
assert(segmentsIntersect([0, 0], [3, 3], [2, 2], [5, 5]));
assert(segmentsIntersect([0, 0], [2, 0], [2, 0], [2, 5]));
assert(!segmentsIntersect([0, 0], [4, 0], [1, 1], [3, 2]));
assert(twiceSignedArea([[1, 1], [5, 0], [6, 4], [3, 6], [0, 4]]) === 47); // area 23.5
const u: P[] = [[0, 0], [6, 0], [6, 5], [4, 5], [4, 2], [2, 2], [2, 5], [0, 5]];
assert(pointInPolygon([1, 4], u) === 1 && pointInPolygon([3, 4], u) === -1);
assert(pointInPolygon([3, 2], u) === 0 && pointInPolygon([5, 2], u) === 1);
assert(pointInPolygon([-1, 2], u) === -1);
assert(windingNumber([1, 4], u) === 1 && windingNumber([3, 4], u) === 0);
assert(JSON.stringify(convexHull([[0, 0], [4, 0], [2, 0], [4, 4], [0, 4], [2, 2], [1, 3], [4, 2]])) ===
  JSON.stringify([[0, 0], [4, 0], [4, 4], [0, 4]]));

let seed = 8;
const rand = (m: number): number => {
  seed = (seed * 1103515245 + 12345) % 2147483648;
  return seed % m;
};
for (let t = 0; t < 400; t++) {
  const n = 1 + rand(12);
  const pts: P[] = Array.from({ length: n }, (): P => [rand(9) - 4, rand(9) - 4]);
  const hull = convexHull(pts), h = hull.length;
  if (h >= 3) {
    for (let i = 0; i < h; i++) assert(cross(hull[i], hull[(i + 1) % h], hull[(i + 2) % h]) > 0);
    for (const p of pts) {
      for (let i = 0; i < h; i++) assert(cross(hull[i], hull[(i + 1) % h], p) >= 0);
      assert(pointInPolygon(p, hull) >= 0);
    }
  }
  const uniq = [...pts].sort(byXY).filter((p, i, arr) => i === 0 || byXY(p, arr[i - 1]) !== 0);
  const extreme = uniq.filter((p) => isExtreme(p, uniq.filter((q) => byXY(p, q) !== 0)));
  assert(JSON.stringify([...hull].sort(byXY)) === JSON.stringify(extreme), JSON.stringify(pts));
}
console.log("all geometry tests passed");

Language notes:

  • Overflow. Java and C++ use long/long long; the cross product is exact for coordinates up to . TypeScript uses doubles, which represent integers exactly only up to , so cross is exact only while coordinates stay below about in absolute value; switch to BigInt beyond that. Python integers never overflow.
  • Sorting. Java's TreeSet and C++'s sort + unique sort and deduplicate in one go; in Python sorted(set(points)) does the same.
  • Memory. The Java and C++ hulls use one array of size for both chains (the classic contest form); the second loop starts from index because the rightmost point is already on the stack, and stops popping at t = k + 1 so it never eats the lower chain.

Real-world uses

  • GIS and maps. Every spatial database is built on these predicates. PostGIS (PostgreSQL's spatial extension) calls the GEOS library, a C++ port of the Java Topology Suite (JTS); ST_Contains, ST_Intersects and ST_Area are point-in-polygon, segment intersection and shoelace at heart, with an R-tree (Spatial Trees) to avoid testing every polygon. JTS computes orientation with extended-precision "double-double" arithmetic to avoid the robustness failures shown above. Geofences ("is this driver inside the airport pickup zone?") are point-in-polygon tests after an index lookup; see Geospatial Engineering and Spatial Indexing. The GeoJSON standard (RFC 7946, 2016) even recommends an orientation, the "right-hand rule": exterior rings counter-clockwise, holes clockwise, which you check with the sign of the shoelace sum.
  • Collision detection in games and physics. Physics engines split collision detection into a broad phase (which pairs might touch: sweep-and-prune, a 1-D sweep line over bounding boxes, or a dynamic AABB tree) and a narrow phase on convex shapes. Box2D's (v2) polygon–polygon test uses the separating axis theorem: two convex polygons are disjoint iff some edge normal separates their projections (an check of dot products). Box2D and Bullet use the GJK algorithm (Gilbert, Johnson and Keerthi, 1988) for distances between convex shapes, which works on the Minkowski difference of the two shapes through support points; non-convex shapes are decomposed into convex pieces first. Bullets that move fast are tested as swept segments against walls: segment intersection.
  • Robotics and motion planning. Lozano-Pérez and Wesley (1979) and Lozano-Pérez (1983) planned paths for a convex robot by "growing" every obstacle by the robot's shape (a Minkowski sum, computed from convex hulls), shrinking the robot to a point; the shortest path among polygonal obstacles then runs along the visibility graph of obstacle corners, searched with Dijkstra or A*. Lidar scans are turned into obstacle outlines with hulls; grasp planners and footstep planners test stability with point-in-convex-polygon (is the centre of mass over the support polygon?).
  • Computer graphics. Rasterisers decide which pixels a triangle covers with three edge functions, which are orientation tests evaluated per pixel (Pineda, 1988; the basis of GPU rasterisation). Vector graphics fill shapes with the even–odd or non-zero winding rule (SVG fill-rule, PostScript, PDF). Font outlines are polygons and curves filled the same way.
  • Robust geometry libraries. CGAL (the Computational Geometry Algorithms Library) offers kernels with exact predicates; Shewchuk's adaptive predicates (1997) are used in his Triangle mesh generator and in many meshers since. These exist precisely because of the floating-point failures in this lesson.
  • Data science. scipy.spatial.ConvexHull wraps Qhull (Quickhull, Barber, Dobkin and Huhdanpaa, 1996), also used by MATLAB's convhull. Hulls give outlier "peeling" depths, bounding regions of clusters, and the "convex hull trick" in optimisation (DP Optimizations).

Pitfalls & edge cases

  • Overflow in cross. Coordinates up to need 64-bit products; up to need 128-bit. In Java, int * int overflows silently before being widened: cast first.
  • Floating-point equality. cross == 0 on doubles is almost never what you want, and abs(cross) < 1e-9 is scale-dependent. Prefer integers; see the robustness section.
  • atan2 for sorting. Sorting by angle with atan2 mis-orders nearly equal angles and is slower. Compare with the cross product (within a half-plane), as in Graham's comparator.
  • Duplicate points break both hull algorithms in subtle ways (a zero-length "edge" has orientation 0 with everything). Deduplicate first.
  • All points collinear, or only 1–2 distinct points. Decide the output, and test it: the strict hull returns the two extremes; the "keep collinear" variant must deduplicate.
  • Wrong pop condition. < 0 vs <= 0 silently keeps or drops collinear boundary points. Know which one the problem wants.
  • Orientation of the input polygon. Algorithms that assume counter-clockwise input (convex point-in-polygon by binary search, polygon clipping, offsetting) give garbage on clockwise input. Check the sign of the shoelace sum and reverse if needed.
  • Closed-polygon convention. Some formats repeat the first vertex at the end (GeoJSON does, and so does Shapely's coords). The shoelace sum is unaffected (the extra term is zero), but vertex counts, hull inputs and edge loops can double-count. Strip the repeat.
  • Point on the boundary. Ray casting returns an arbitrary answer for points on edges. Test the boundary first.
  • Vertex on the ray. Use the half-open rule (a.y > p.y) != (b.y > p.y); never >= on both ends.
  • Self-intersecting polygons. Shoelace and even–odd assume a simple polygon. Validate input (OGC "valid" geometries) or use the winding number.
  • Screen coordinates. With pointing down, "counter-clockwise" in maths is clockwise on screen. Flip or flip your expectations.
  • Latitude/longitude are not planar. A polygon spanning hundreds of kilometres, or crossing the antimeridian (), needs a projection or spherical geometry (Google's S2 library works on the sphere). Shoelace on raw degrees does not give square metres. See Geospatial Engineering.

Variations

  • Point in convex polygon in . Binary search over the fan of triangles from vertex 0.
  • Dynamic hull. Insert points online and keep the hull: easy for insertions only (a balanced BST per chain, amortised); with deletions, Overmars and van Leeuwen (1981) give per update.
  • 3-D convex hull. too (Preparata–Hong divide and conquer, randomised incremental, Quickhull). The output is a polyhedron of faces. Qhull does any dimension.
  • Convex hull trick and Li Chao trees. In DP transitions of the form , the useful lines form a lower hull; queries walk it. See DP Optimizations.
  • Minkowski sum of convex polygons in : merge the edge vectors by angle. Powers configuration-space obstacles and GJK.
  • Polygon clipping. Sutherland–Hodgman (1974) clips a polygon against a convex window edge by edge using orientation tests; Weiler–Atherton and Greiner–Hormann handle general polygons.
  • Triangulation. Ear clipping triangulates a simple polygon in ; Delaunay triangulation (maximise the minimum angle) is the dual of the Voronoi diagram, both (Fortune's sweep, 1987). Their key predicate is "in-circle", a determinant, the 2-D sibling of orientation.
  • Minimum enclosing circle in expected by Welzl's randomised algorithm (1991); see Randomized Algorithms.
  • Line sweep for the closest pair, rectangle union and segment problems, and the general "events + ordered status" pattern in Intervals.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Check If It Is a Straight Line (LeetCode 1232) — Decide whether all given points are collinear. Teaches the orientation test with no division (no slopes, no division by zero).

Hint

For every point , cross(points[0], points[1], p) == 0.

2. Largest Triangle Area (LeetCode 812) — Largest area of a triangle formed by three of the given points. Teaches area as half the absolute cross product.

Hint

: try all triples, area . (The optimal triangle's corners are hull vertices, which leads to faster methods.)

3. Valid Square (LeetCode 593) — Do four points, in any order, form a square? Teaches squared distances and degenerate inputs (repeated points).

Hint

Compute the 6 squared pairwise distances. A square has exactly two distinct values, the smaller (sides) appearing 4 times and the larger (diagonals) twice, and the smaller is not 0.

4. Rectangle Area (LeetCode 223) — Total area covered by two axis-aligned rectangles. Teaches overlap of intervals in each axis, the warm-up for Rectangle Area II.

Hint

Area A + area B − overlap, where overlap width is max(0, min(ax2, bx2) - max(ax1, bx1)), and the same for height.

5. Point Location Test (CSES 2189) — For each test, say whether a point is to the left of, to the right of, or on a directed line. The orientation test, with coordinates up to .

Solution

One cross product per test, in 64-bit integers.

import sys


def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    out = []
    for k in range(t):
        x1, y1, x2, y2, x3, y3 = map(int, data[1 + 6 * k: 7 + 6 * k])
        c = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
        out.append("LEFT" if c > 0 else "RIGHT" if c < 0 else "TOUCH")
    print("\n".join(out))


main()

6. Line Segment Intersection (CSES 2190) — Do two segments intersect? Collinear and touching cases included. Teaches the full test from this lesson.

Hint

segments_intersect from the implementation section, verbatim.

7. Polygon Area (CSES 2191) — Area of a polygon given its vertices in order; print twice the area. Teaches the shoelace formula and keeping the result an integer.

Solution

The problem asks for , which is an integer: the absolute value of the shoelace sum. No division at all.

import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    pts = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
    s = sum(pts[i][0] * pts[(i + 1) % n][1] - pts[(i + 1) % n][0] * pts[i][1] for i in range(n))
    print(abs(s))


main()

8. Point in Polygon (CSES 2192) — For many points, inside / outside / on the boundary of one polygon. Teaches the three-way ray-casting test with all the edge cases.

Hint

point_in_polygon from the implementation, mapping 1, −1, 0 to INSIDE, OUTSIDE, BOUNDARY. The polygon is fixed and small enough that per query passes.

9. Polygon Lattice Points (CSES 2193) — Count lattice points strictly inside and on the boundary of a polygon. Pick's theorem.

Solution

over the edges; from the shoelace sum; . All integer.

import sys
from math import gcd


def lattice_points(pts):
    n = len(pts)
    a2 = abs(sum(pts[i][0] * pts[(i + 1) % n][1] - pts[(i + 1) % n][0] * pts[i][1] for i in range(n)))
    b = sum(gcd(abs(pts[i][0] - pts[(i + 1) % n][0]), abs(pts[i][1] - pts[(i + 1) % n][1])) for i in range(n))
    return (a2 - b + 2) // 2, b


assert lattice_points([(0, 0), (6, 0), (4, 4), (0, 2)]) == (11, 12)   # the Pick example above

10. Convex Hull (CSES 2195) — Output the hull of up to points, including points on the hull's edges. Teaches the keep-collinear variant and the all-collinear trap.

Hint

Monotone chain with cross < 0 as the pop condition, then deduplicate. Same code as problem 12.

11. Minimum Euclidean Distance (CSES 2194) — Smallest squared distance between two of up to points. Closest pair.

Hint

Divide and conquer as in the closest-pair section of Divide & Conquer, or a sweep with a set ordered by . Output the squared distance, so stay in integers.

12. Erect the Fence (LeetCode 587) — Return every tree on the fence that encloses all trees: the convex hull including collinear boundary points. Teaches the < 0 pop condition.

Solution

Popping only on strict right turns keeps collinear points. When all points are collinear, both chains contain all of them, so return a set.

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def outer_trees(trees):
    pts = sorted(set(map(tuple, trees)))
    if len(pts) <= 2:
        return [list(p) for p in pts]
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0:   # pop only on a right turn
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0:
            upper.pop()
        upper.append(p)
    return [list(p) for p in set(lower + upper)]                       # all-collinear input repeats points


assert sorted(outer_trees([[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]])) == [[1, 1], [2, 0], [2, 4], [3, 3], [4, 2]]
assert sorted(outer_trees([[1, 2], [2, 2], [4, 2]])) == [[1, 2], [2, 2], [4, 2]]

Checked against a brute-force "is the point on an edge of the strict hull?" oracle on 3,000 random inputs.

13. Max Points on a Line (LeetCode 149) — Most points on one straight line. Teaches representing a direction exactly (reduced (dx, dy) with a sign convention) instead of a floating slope.

Hint

For each anchor point, group the others by direction (dx/g, dy/g) with g = gcd(dx, dy), normalised so the first non-zero component is positive. .

14. Rectangle Area II (LeetCode 850) — Area of the union of up to 200 rectangles, modulo . The sweep line with coordinate compression.

Solution

Sweep over . Between consecutive events, add (covered -length) × (gap in ). Keep a cover count per elementary -slab. here, which is plenty for ; a segment tree makes it .

def rectangle_area(rects):
    MOD = 10**9 + 7
    ys = sorted({y for _, y1, _, y2 in rects for y in (y1, y2)})
    idx = {y: i for i, y in enumerate(ys)}
    events = sorted([(x1, 1, y1, y2) for x1, y1, x2, y2 in rects] +
                    [(x2, -1, y1, y2) for x1, y1, x2, y2 in rects])
    cover = [0] * (len(ys) - 1)          # how many rectangles cover each elementary y-slab
    area, prev_x = 0, events[0][0]
    for x, delta, y1, y2 in events:
        covered = sum(ys[i + 1] - ys[i] for i, c in enumerate(cover) if c > 0)
        area += covered * (x - prev_x)   # strip between the previous event and this one
        for i in range(idx[y1], idx[y2]):
            cover[i] += delta
        prev_x = x
    return area % MOD


assert rectangle_area([[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]]) == 6
assert rectangle_area([[0, 0, 1000000000, 1000000000]]) == 49

Checked against counting unit cells on 2,000 random small inputs.

Common mistakes & interview follow-ups

"Why not compute slopes?" Slopes divide (vertical lines break them), are inexact in floating point, and lose the direction (a slope cannot tell left from right). The cross product does all of it with two multiplications and no division.

"What if the coordinates are doubles?" Say what can go wrong (the 672 wrong signs above), then offer: scale to integers if the precision is known; otherwise use exact/adaptive predicates (Shewchuk, CGAL) for decisions and floats only for measurements; an epsilon as a last resort, scaled to the input magnitude.

"Graham or Andrew?" Same complexity. Andrew sorts by coordinates (no angle comparator, no pivot special cases) and handles collinear points uniformly; Graham gives the points in angular order around the pivot, which some problems want.

"Your hull is wrong on collinear points." Ask which output is required, then switch between <= 0 and < 0 and handle the all-collinear case.

"Can you do better than ?" Not in general (the parabola reduction from sorting). Output-sensitively, (Chan). If points are already sorted, . If coordinates are small integers, sort them with counting/radix sort (Non-Comparison Sorts) for overall.

"Inside a polygon with a million vertices, many queries?" Preprocess: for a convex polygon, binary search (); for a general polygon, a trapezoidal decomposition or slab method gives queries; in practice, an R-tree over edges plus ray casting against only the edges whose -range covers the query.

"Farthest pair in ." Hull, then rotating calipers. Then explain why the farthest pair must be hull vertices.

Mistakes interviewers watch for: dividing to compute an intersection when only a yes/no was asked; int overflow in the cross product; ray casting without the half-open rule; forgetting to deduplicate; returning the first hull point twice; mixing up clockwise and counter-clockwise when the axis points down.

Quick quiz

1. , , . Left turn, right turn or straight?

Answer

: left turn (counter-clockwise).

2. Segments and . Do they intersect, and which part of the test says so?

Answer

Yes, they share the endpoint . The proper-crossing test fails ( values include zeros); the endpoint check finds on the other segment.

3. The shoelace sum of a polygon is . What does that tell you?

Answer

Area ; vertices listed clockwise. Reverse the list for counter-clockwise.

4. In the monotone chain trace, why is D popped when H arrives?

Answer

B, D, H are collinear (cross = 0), and the strict hull pops on <= 0, so D, which lies in the middle of the bottom edge B–H, is not a corner.

5. A polygon has vertices on lattice points, area 10 and 8 boundary lattice points. How many interior lattice points?

Answer

Pick: .

6. Why can the farthest pair of points be found among hull vertices only?

Answer

For any segment with not a hull vertex, lies in the hull, which is convex; the distance from is a convex function, so its maximum over the hull is attained at a vertex. Replacing by that vertex does not decrease the distance.

Further reading / sources

  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008 — chapter 1 (convex hulls, robustness), chapter 2 (line segment intersection, Bentley–Ottmann with degeneracies), chapter 4 (half-plane intersection and LP).
  • Joseph O'Rourke, Computational Geometry in C, 2nd ed., Cambridge, 1998 — the most code-focused textbook; chapter 1 (area, segment intersection), chapter 3 (hulls).
  • Franco P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer, 1985.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 3rd ed. chapter 33 (segment intersection, sweep, Graham scan, Jarvis march, closest pair).
  • R. L. Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set", Information Processing Letters 1(4), 1972.
  • A. M. Andrew, "Another efficient algorithm for convex hulls in two dimensions", Information Processing Letters 9(5), 1979.
  • R. A. Jarvis, "On the identification of the convex hull of a finite set of points in the plane", Information Processing Letters 2(1), 1973.
  • Timothy M. Chan, "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete & Computational Geometry 16, 1996.
  • Michael I. Shamos and Dan Hoey, "Geometric intersection problems", 17th IEEE FOCS, 1976; Jon L. Bentley and Thomas A. Ottmann, "Algorithms for reporting and counting geometric intersections", IEEE Transactions on Computers C-28(9), 1979.
  • Godfried Toussaint, "Solving geometric problems with the rotating calipers", Proc. IEEE MELECON '83, 1983.
  • Jonathan R. Shewchuk, "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates", Discrete & Computational Geometry 18(3), 1997.
  • Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap, "Classroom Examples of Robustness Problems in Geometric Computations", Computational Geometry: Theory and Applications 40(1), 2008.
  • cp-algorithms.com, Geometry section: oriented area, segment intersection, area of a polygon, convex hull, Pick's theorem.
  • CSES Problem Set, Geometry section — seven graded problems that cover this lesson.

Lessons: previous — FFT & NTT · next — Game Theory · module — Math · course — DSA: Zero to Mastery

Related Archon pages: Divide & Conquer · Spatial Trees · Segment Trees · Monotonic Stack & Deque · Intervals · Geospatial Engineering · Spatial Indexing