Chapter 8: Geometry

Overview

Computational geometry is the least forgiving topic in competitive programming — one wrong epsilon and you get WA on test 47. But when geometry problems appear (and they do, regularly), there's no substitute for knowing these techniques. This chapter starts with the essential primitives (cross product, orientation test) that are the building blocks for everything, then covers convex hull, rotating calipers, and half-plane intersection. The good news: once you nail the basics, most contest geometry reduces to a few clean patterns.

Navigation

Coming from: Chapter 7 — Mathematics — number theory, combinatorics, and game theory
Going to: Chapter 9 — Offline Techniques — sweep line, Mo's algorithm, and query reordering

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	Geometry Basics	Beginner	"Cross product," "orientation test," "point-in-polygon"
02	Convex Hull	Intermediate	"Smallest convex polygon containing all points"
03	Rotating Calipers	Advanced	"Diameter of point set" or "farthest pair"
04	Half-Plane Intersection	Advanced	"Region satisfying linear inequalities" or "polygon kernel"
05	Point in Polygon	Intermediate	"Is this point inside the polygon?"
06	Closest Pair	Intermediate	"Minimum distance between any two points"
07	Half-Plane Intersection — Contest Template	Advanced	Lean paste-ready template companion to 04
08	Rotating Calipers — Contest Template	Advanced	Lean paste-ready template companion to 03
09	Sweep Line Geometry	Advanced	"Segment intersection," "rectangle union area"
10	Geometry Recipes	Intermediate	"Point-to-line distance," "circle intersection," "rotation"
11	Floating-Point Gotchas	Required	"WA on test 47" — read this before any geometry submission

About files 03/08 and 04/07: files 03 and 04 are the conceptual lessons (intuition, proofs, walkthroughs, applications). Files 08 and 07 are the lean contest templates — minimal prose around a single tested implementation. Read the lesson once; keep the template open during contests.

If You Only Read 3 Files

1. Geometry Basics — because the cross product and orientation test are the atoms of computational geometry. Every other algorithm in this chapter (and most geometry problems on CF) builds on them.
2. Convex Hull — because Andrew's monotone chain is the most commonly needed geometry algorithm in contests. It's the answer to "farthest pair," "maximum area triangle," and many optimization problems on point sets.
3. Geometry Recipes — because when geometry appears as a subtask in a non-geometry problem, you need compact, tested formulas you can paste immediately. This file is your emergency kit.

And keep Floating-Point Gotchas at hand — geometry's failure mode is almost never "wrong algorithm," it's "right algorithm, wrong epsilon."

Cross-Chapter Connections

• Geometry Basics uses Sorting from Chapter 1 (angle sorting for polar order)
• Convex Hull often combines with Binary Search for tangent-line queries
• Half-Plane Intersection connects to Sweep Line in Chapter 9 — both process sorted geometric events
• Sweep Line Geometry is the geometry-specific counterpart of the general Sweep Line in Chapter 9
• Closest Pair can be solved with either divide-and-conquer or sweep line — bridges algorithmic paradigms
• Geometry problems sometimes require Coordinate Compression from Chapter 1 when dealing with large coordinates
• For the convex hull trick in DP (different from the geometric convex hull!), see DP — Convex Hull Trick in Chapter 4

---

File Listing

File	Topic	Level
geometry-basics	Geometry Basics	⭐
convex-hull	Convex Hull	⭐⭐
rotating-calipers	Rotating Calipers (lesson)	⭐⭐⭐
half-plane-intersection	Half-Plane Intersection (lesson)	⭐⭐⭐
point-in-polygon	Point in Polygon	⭐⭐
closest-pair	Closest Pair of Points	⭐⭐
half-plane-intersection-template	Half-Plane Intersection (contest template)	⭐⭐⭐
rotating-calipers-template	Rotating Calipers (contest template)	⭐⭐⭐
sweep-line-geometry	Sweep Line for Geometry	⭐⭐⭐
geometry-recipes	Geometry Recipes	⭐⭐
floating-point-gotchas	Floating-Point Gotchas	⭐⭐

Suggested Reading Order

1. geometry-basics — cross product, orientation test, foundational primitives
2. floating-point-gotchas — read this alongside basics; integer-vs-floating choice should be made before you write any geometry code
3. convex-hull — Andrew's monotone chain algorithm
4. point-in-polygon — ray casting, winding number, O(log n) for convex
5. closest-pair — divide-and-conquer and sweep-line approaches
6. rotating-calipers — diameter and extremal measurements on convex hulls
7. half-plane-intersection — intersect half-planes for LP and polygon kernels
8. sweep-line-geometry — segment intersection, rectangle union area
9. geometry-recipes — compact reference for common subroutines