EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Data Structures & Algorithms

Geometry

The intended emphasis is contest geometry that survives integer arithmetic, not coordinate-free elegance for its own sake.

6 published notes
3 planned topics
2 advanced or expert notes
basic starting level
Back to DSA Competitive Programming
Category Overview

Geometry

Reliable primitives first, then hulls, sweeps, and polygon routines.

Raw TeX

Overview

Geometry notes will stay deliberately narrow: sturdy predicates first, then the contest routines that grow out of them. The main goal is to avoid fragile floating-point reasoning when integer geometry is enough.

Scope

The current coverage starts with the integer-geometry basics that most later routines depend on: orientation tests, segment interaction, hull construction, and polygon classification. From there the natural next layer is calipers, closest-pair style routines, and more global sweep-line reductions.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 1 intermediate: 3 advanced: 2 expert: 0
1 basic
basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

Orientation and Cross Product

3 intermediate
intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Convex Hull, Line Intersection, Point in Polygon

2 advanced
advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

Rotating Calipers, Closest Pair

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

01
basic

Orientation and Cross Product

The core integer-geometry predicate behind turns, area tests, segment intersection, and hull construction.

geometry primitives integer geometry / predicates
02
intermediate

Convex Hull

Build the outer envelope of a point set with monotone chain and use it as the basis for many geometry reductions.

geometry convex hull / monotone chain
03
intermediate

Line Intersection

Reliable line and segment intersection tests built on orientation, with exact predicates and careful boundary handling.

segments predicates / integer geometry
04
intermediate

Point in Polygon

Classify a point as outside, on the boundary, or inside a polygon with a contest-ready ray-crossing routine.

polygons classification / integer geometry
05
advanced

Rotating Calipers

Walk two pointers around a convex polygon to enumerate antipodal structure without restarting from scratch.

convex polygon two pointers / geometry
06
advanced

Closest Pair

Find the nearest pair of points in O(n log n) with divide and conquer and a y-sorted strip check.

divide and conquer geometry / nearest pair
Study Order

Recommended order to read this branch

The default order follows each note's dependency weight: early notes establish primitives, later notes reuse them or assume the same invariants without re-explaining them.

01
basic

Orientation and Cross Product

The core integer-geometry predicate behind turns, area tests, segment intersection, and hull construction.

geometry primitives integer geometry / predicates
02
intermediate

Convex Hull

Build the outer envelope of a point set with monotone chain and use it as the basis for many geometry reductions.

geometry convex hull / monotone chain
03
intermediate

Line Intersection

Reliable line and segment intersection tests built on orientation, with exact predicates and careful boundary handling.

segments predicates / integer geometry
04
intermediate

Point in Polygon

Classify a point as outside, on the boundary, or inside a polygon with a contest-ready ray-crossing routine.

polygons classification / integer geometry
05
advanced

Rotating Calipers

Walk two pointers around a convex polygon to enumerate antipodal structure without restarting from scratch.

convex polygon two pointers / geometry
06
advanced

Closest Pair

Find the nearest pair of points in O(n log n) with divide and conquer and a y-sorted strip check.

divide and conquer geometry / nearest pair
Planned topics

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Half-plane intersection planned Sweep line outline KD-tree outline
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Category TeX sourcecompetitive_programming/dsa/geometry/index.tex