Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 63 ยท Math for Contests

Geometry Toolkit for Contests

A contest geometry toolkit in Python: exact cross products, segment intersection, convex hull, point in polygon, rotating calipers and precision rules.

Geometry problems have a reputation for being painful, and most of that pain comes from two sources: special cases (collinear points, touching segments, duplicate points) and precision (floating-point numbers that are almost but not exactly equal). A small toolkit built on exact integer arithmetic removes both. Every function here uses only integer addition, subtraction and multiplication, so results are exact in Python for any size of input.

This lesson gives you that toolkit: the cross product and orientation, segment intersection with all the edge cases, the convex hull, point-in-polygon, the farthest pair of points via rotating calipers, and the precision rules for the rare moment you must use floats. Each tool is checked against an independent brute force. The background is in Computational Geometry Basics and Pick's theorem and half-planes.

Vectors: the basic toolkit

A geometric algorithm is a procedure on points, lines, segments and polygons. Nearly all of them are built from a few vector operations, so write those first.

A vector is a pair (or triple) of numbers, a displacement. The vector from point a to point b is b - a, taken coordinate by coordinate.

  • Addition and subtraction work coordinate by coordinate. u + v is "walk along u, then along v"; u - v points from the end of v to the end of u.
  • Scaling multiplies every coordinate: 2u has twice the length in the same direction.
  • Dot product u . v = ux*vx + uy*vy (+ uz*vz). It equals |u| |v| cos(angle). So it is zero for perpendicular vectors, positive for an acute angle and negative for an obtuse one. u . u is the squared length, which avoids a square root.
  • Cross product in 2D ux*vy - uy*vx is a single number: the signed area of the parallelogram spanned by u and v. Its sign tells whether v is counter-clockwise (positive), clockwise (negative) or parallel (zero) from u. Half its absolute value is a triangle's area. The next section builds orientation on it.
  • Cross product in 3D gives a vector: (y1*z2 - y2*z1, z1*x2 - z2*x1, x1*y2 - x2*y1) for (x1, y1, z1) and (x2, y2, z2). It is perpendicular to both inputs, and its length is the area of the parallelogram. Use it for the normal of a plane through three points, or for the volume of a box (the scalar triple product (a x b) . c).

Two derived formulas appear constantly. The distance from point p to the line through a and b is |cross(b - a, p - a)| / |b - a|, the parallelogram area divided by its base. The closest point on a segment is found by projecting: compute t = (p - a) . (b - a) / ((b - a) . (b - a)), clamp t to [0, 1], and take a + t (b - a).

Keep coordinates as integers while you only add, subtract, multiply and compare. Use floats only for the final division or square root.

Python Vector operations, 3D cross product and distances

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cross product and orientation

For vectors u = (ux, uy) and v = (vx, vy), the cross product is ux*vy - uy*vx. For three points a, b, c define

TEXT
cross(a, b, c) = (b - a) x (c - a)
  • positive: c is to the left of the directed line a -> b (counter-clockwise turn),
  • negative: c is to the right (clockwise turn),
  • zero: the three points are collinear.

Half of all geometry code is calls to cross, and it is exact with integer coordinates. Its absolute value is twice the area of triangle a, b, c.

Segment intersection with every special case

Two segments p1p2 and p3p4 intersect (touching counts) in two situations:

  1. General case: p3 and p4 lie on opposite sides of line p1p2, and p1 and p2 lie on opposite sides of line p3p4. The orientation signs must differ (a zero counts as "on the line", handled in case 2).
  2. Collinear or touching case: an orientation is zero and the corresponding point lies inside the bounding box of the other segment.
Python Segment intersection with orientation tests, versus exact rational solving

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The small coordinate range (0 to 4) produces many collinear, touching and degenerate pairs, which is exactly where bugs live. The last line shows touching at an endpoint (true) and two collinear but disjoint segments (false).

Convex hull (monotone chain)

Sort the points by (x, y), then build the lower hull and upper hull with a stack, popping while the last turn is not a strict left turn. Remove the duplicated end points and join them. Time is O(n log n). Pop on cross <= 0 to drop collinear points from the boundary, or on cross < 0 to keep them.

Python Convex hull versus gift wrapping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Point in polygon and the polygon area

Area comes from the shoelace formula: sum of x_i*y_{i+1} - x_{i+1}*y_i, half of the absolute value. Keep the doubled value 2A as an integer to avoid fractions.

For point in polygon, shoot a ray to the right and count crossings, treating boundary points first. To keep it exact, never divide: compare cross products. The function below returns 0 for outside, 1 for on the boundary and 2 for strictly inside. We verify it with Pick's theorem: for lattice polygons the interior and boundary counts determine the area.

Python Point in polygon, verified with Pick's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Farthest pair with rotating calipers

The two points that are farthest apart are always vertices of the convex hull. A brute force over the hull is O(h^2). Rotating calipers gets O(h): for each hull edge i -> i+1, move a second pointer j forward while the triangle area keeps growing (the point j gets farther from the edge). The farthest point from each edge sweeps around the hull monotonically, so j only moves forward in total.

Python Farthest pair: rotating calipers versus all pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that squared distances are used throughout: comparisons are exact in integers, and a square root is needed only for the final printed answer, if at all.

Precision rules

  1. Stay in integers whenever coordinates are integers. Cross products of 64-bit values fit in 128 bits (Python has no limit).
  2. If you need division, keep a Fraction or keep numerator and denominator separately.
  3. When floats are unavoidable (angles, circles), compare with a tolerance eps such as 1e-9 scaled to your coordinate size, and never use == on floats.
  4. Prefer comparing squared distances and cross products to computing sqrt and atan2.
Python Why floats fail on collinear points

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A toolkit checklist

Question Tool
Left, right or collinear? cross(a, b, c) sign
Do two segments touch? orientation signs plus bounding-box checks
Smallest convex shape around points monotone chain, O(n log n)
Is a point inside a polygon? Area? ray casting with cross products; shoelace
Farthest pair hull, then rotating calipers, O(n log n) total
Interior and boundary lattice points Pick's theorem with gcd

Common mistakes: forgetting duplicate points before the hull, popping on the wrong sign (which keeps or drops collinear points unintentionally), treating touching segments as non-intersecting, and mixing floats into an exact pipeline.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a negative value of cross(a, b, c) mean?

    Positive means a counter-clockwise (left) turn, negative a clockwise (right) turn, zero collinear.
  2. 2. Two segments lie on the same line and do not overlap. What does the orientation-only test d1d2 < 0 and d3d4 < 0 give?

    All four orientation values are zero in the collinear case, so the strict opposite-side test fails; the bounding-box checks decide whether the segments overlap.
  3. 3. In the monotone chain hull, which pop condition removes collinear boundary points?

    A point that makes a zero turn is collinear with its neighbors; popping on cross <= 0 removes it, while cross < 0 would keep it.
  4. 4. Why are squared distances preferred when comparing distances?

    Comparing squares gives the same order as comparing distances, and integers have no rounding error.

Summary

  • Build everything on cross(a, b, c) with integer coordinates: its sign gives left, right or collinear.
  • Segment intersection needs the opposite-sides test plus bounding-box checks for collinear and touching cases.
  • The monotone chain hull runs in O(n log n); the pop condition decides whether collinear points stay.
  • Point in polygon uses cross products only; Pick's theorem is a handy cross-check. Rotating calipers finds the farthest pair in linear time after the hull.
  • Use exact integers or fractions, compare squared distances, and use an eps only when floats cannot be avoided.

Next: Data Structures in Contest Practice