Appearance
Geometry Basics
Quick Revisit
- USE WHEN: any 2D geometry problem -- orientation tests, area computation, point-in-polygon
- INVARIANT: cross(B-A, C-A) > 0 means C is left of directed line A->B; = 0 means collinear
- TIME: O(1) per orientation test, O(n) for polygon area | SPACE: O(1)
- CLASSIC BUG: integer overflow in cross product when coordinates are up to 10^9
- PRACTICE: ../12-practice-ladders/08-ladder-mixed.md
GEO-01 | The portable primitives every geometry algorithm builds on: point/vector type, cross and dot products, orientation tests, signed area, and the overflow policy for integer coordinates. Convex hull and point-in-polygon are introduced briefly here as the motivating examples for orientation tests, but each has a dedicated file (02-convex-hull, 05-point-in-polygon) for the full treatment.
Difficulty: [Intermediate]Prerequisites: SortingCF Rating Range: 1400 -- 2000
Contest Frequency: [*] Specialized -- appears in geometry-themed contests
Contents
- 1. Intuition & Concept
- 2. C++ STL / Language Reference
- 3. Implementation (Contest-Ready)
- 4. Operations Reference
- 5. Problem Patterns & Tricks
- 6. Contest Cheat Sheet
- 7. Gotchas & Debugging
- Self-Test
- 9. Practice Problems
- 10. Further Reading
Intuition & Concept
Layer 1 -- The Pain
You have 8 points in 2D:
A(1,1) B(3,1) C(5,2) D(6,4)
E(4,5) F(2,5) G(0,3) H(3,3)Problem: find the convex hull -- the smallest convex polygon enclosing all points. Think of it as the rubber band stretched around nails.
Naive approach: for every ordered triple
Even the smarter "check every edge" variant is
| Time at | ||
|---|---|---|
| 10 s | ||
| ~115 days |
We're testing every possible triple, even triples that are clearly interior. The points are in 2D -- geometry is structured. There has to be a better way.
Layer 2 -- The Key Insight
The cross product tells you whether three points turn left or right. Sort points by x-coordinate, sweep left-to-right for the lower hull and right-to-left for the upper hull; in each pass the surviving chain stays strictly counter-clockwise (positive cross). Total cost:
dominated by the sort.
Sign-convention note (read once, stick to it for the rest of the chapter): this file uses cross(A, B, C) > 0 for a counter-clockwise (CCW, "left") turn and < 0 for a clockwise (CW, "right") turn. With the same sign rule, both lower and upper hull passes pop while cross(stack[-2], stack[-1], P) <= 0 — that is, while the new triple is not a strict left turn. The two passes differ only in iteration direction, never in the sign test.
Analogy: Imagine walking along the coastline of an island, always turning left. If you ever turn right, you've cut inland — backtrack to the last headland and continue. Sorting gives you the starting direction; the cross-product sign is your compass.
Where the analogy breaks: on a real coast you follow a continuous curve. Here we jump between discrete points, so "backtracking" means popping from a stack.
Layer 3 -- Visual Walkthrough
Same 8 points. Sort by x (break ties by y):
Sorted: G(0,3) A(1,1) F(2,5) H(3,3) B(3,1) E(4,5) C(5,2) D(6,4)
Index: 0 1 2 3 4 5 6 7Cross product recap: for points
- Positive
left turn (counter-clockwise) - Zero
collinear - Negative
right turn (clockwise)
Cross Product Orientation Test:
C cross > 0 C
/ (CCW / left) \ cross < 0
/ \ (CW / right)
A------>B A------>B
A------B------C cross = 0
(collinear)Build LOWER hull -- sort by (x, y), sweep left to right, and pop while the new triple is not a strict left turn (cross <= 0). What survives is a chain that turns counter-clockwise at every vertex — geometrically, the bottom boundary of the hull, traced left to right.
y
5 | F E
4 | D
3 | G H
2 | C
1 | A B
0 +--+--+--+--+--+--+--+---> x
0 1 2 3 4 5 6 7 Sorted by (x, then y):
G(0,3) A(1,1) F(2,5) B(3,1) H(3,3) E(4,5) C(5,2) D(6,4)
LOWER HULL -- pop while |stack| >= 2 and cross(stack[-2], stack[-1], P) <= 0
Push G(0,3) Stack: [G]
Push A(1,1) Stack: [G, A]
F(2,5): cross(G,A,F) = (1-0)(5-3)-(1-3)(2-0) = 2-(-4) = 6 > 0
Keep. Push F. Stack: [G, A, F]
B(3,1): cross(A,F,B) = (2-1)(1-1)-(5-1)(3-1) = 0-8 = -8 <= 0
Pop F. Stack: [G, A]
cross(G,A,B) = (1-0)(1-3)-(1-3)(3-0) = -2+6 = 4 > 0
Keep. Push B. Stack: [G, A, B]
H(3,3): cross(A,B,H) = (3-1)(3-1)-(1-1)(3-1) = 4-0 = 4 > 0
Keep. Push H. Stack: [G, A, B, H]
E(4,5): cross(B,H,E) = (3-3)(5-1)-(3-1)(4-3) = 0-2 = -2 <= 0
Pop H. Stack: [G, A, B]
cross(A,B,E) = (3-1)(5-1)-(1-1)(4-1) = 8-0 = 8 > 0
Keep. Push E. Stack: [G, A, B, E]
C(5,2): cross(B,E,C) = (4-3)(2-1)-(5-1)(5-3) = 1-8 = -7 <= 0
Pop E. Stack: [G, A, B]
cross(A,B,C) = (3-1)(2-1)-(1-1)(5-1) = 2-0 = 2 > 0
Keep. Push C. Stack: [G, A, B, C]
D(6,4): cross(B,C,D) = (5-3)(4-1)-(2-1)(6-3) = 6-3 = 3 > 0
Keep. Push D. Stack: [G, A, B, C, D]
Lower hull: G -> A -> B -> C -> D y
5 | . .
4 | D
3 | G . /
2 | C--+
1 | A------B--+
0 +--+--+--+--+--+--+--+---> x
0 1 2 3 4 5 6UPPER HULL -- iterate the same sorted list right-to-left with the same pop rule. Working through it on the same eight points yields D -> E -> F -> G. Concatenating the two chains (and dropping the duplicated endpoints) gives the full hull:
y
5 | F-----------E
4 | / \ D
3 | G /
2 | \ C--+
1 | A------B--+
0 +--+--+--+--+--+--+--+---> x
Hull: G -> A -> B -> C -> D -> E -> F -> G
Interior: H(3,3)Convention notes for downstream algorithms: the implementation below returns the hull in CCW order, with the first vertex not repeated at the end (the duplicate-of-first added during construction is popped before returning). Many downstream routines — rotating calipers, minimum enclosing rectangle, point-in-convex-polygon — assume exactly this layout. If you change the pop rule from
<= 0to< 0(to keep collinear boundary points), the upper- and lower-hull joins need a deduplication pass to avoid emitting the leftmost or rightmost vertex twice.
Operations: 16 cross-product evaluations vs
Layer 4 -- The Invariant
+------------------------------------------------------------------+
| INVARIANT: At every step, the stack forms a convex chain. |
| When adding point P, pop until cross(stack[-2], stack[-1], P) > 0|
| (strictly left turn). Each point is pushed at most once and |
| popped at most once => amortized O(n) for the sweep. |
+------------------------------------------------------------------+Why it holds: if the last three points make a right turn or are collinear, the middle point is inside the convex hull (or on an edge) and can never contribute. Removing it restores convexity. Since each of the
Layer 5 -- When to Reach for This
Trigger phrases:
| Phrase in problem statement | Technique |
|---|---|
| "convex hull" | Andrew's monotone chain |
| "farthest pair of points" | Convex hull + rotating calipers |
| "point inside polygon" | Ray casting / winding number |
Convex polygon: Non-convex polygon:
+-----+ +-----+
/ \ / \
+ + + +----+
\ / \ |
+-----+ +--+
All interior angles < 180 deg Has a "dent" (reflex angle)
Convex: O(log n) point query Non-convex: O(n) ray casting| "area of polygon" | Shoelace formula (cross product sum) | | "minimum enclosing rectangle" | Convex hull + rotating calipers |
Counter-examples -- NOT this technique:
- "Closest pair of points"
divide-and-conquer, not hull. - "Shortest path avoiding polygons"
visibility graph + Dijkstra. - "Number of lattice points inside polygon"
Pick's theorem.
What the Code Won't Teach You
The debugging skill for geometry. When your geometry code is wrong, the bug is almost never a logical error in the algorithm -- it's a sign flip, an off-by-one in epsilon, or a missed case for collinear points. Geometry debugging requires printing intermediate values (cross product signs, sorted orders, orientation tests) and tracing through small, hand-computed examples. The skill of designing these small test cases is separate from knowing the geometry itself.
The hierarchy of precision methods. In rough order from most to least reliable: (1) stay entirely in integers, (2) use exact arithmetic libraries (rare in CP), (3) use floating-point with careful epsilon, (4) use floating-point without epsilon and hope. Most CP geometry problems are designed to be solvable with option 1 or option 3. Knowing which one applies to your problem is the first decision you should make.
The interplay between geometry and problem structure. Many geometry problems in CP aren't purely geometric -- they combine geometry with DP, graph algorithms, or binary search. The geometry part is often just the "hard primitive" and the rest of the solution is standard. Recognizing this decomposition helps you allocate your debugging time correctly: get the geometric primitive rock-solid first, then build the algorithm on top.
C++ STL / Language Reference
Geometry is mostly hand-rolled, but these help:
| Function / Type | Header | What it does | Complexity |
|---|---|---|---|
complex<double> | <complex> | 2D point (real=x, imag=y) | -- |
sort() | <algorithm> | Sort points lexicographically | |
atan2(y,x) | <cmath> | Angle of vector (y,x) in radians | |
hypot(dx,dy) | <cmath> | ||
__int128 | built-in (GCC) | 128-bit int for exact big cross products |
Tip: Prefer integer coordinates with
long longcross products over floating-point whenever possible. Floating-point geometry is an endless source of bugs.
Implementation (Contest-Ready)
Point struct and cross product -- Minimal template
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(P o) const { return {x - o.x, y - o.y}; }
bool operator<(P o) const { return tie(x, y) < tie(o.x, o.y); }
bool operator==(P o) const { return x == o.x && y == o.y; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
ll cross(P o, P a, P b) { return cross(a - o, b - o); }
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }Convex hull -- Andrew's monotone chain
cpp
// Returns convex hull in CCW order. Removes collinear points.
// For collinear points on hull edges, change < 0 to <= 0.
vector<P> convex_hull(vector<P> pts) {
int n = pts.size();
if (n < 2) return pts;
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
n = pts.size();
if (n < 2) return pts;
vector<P> hull;
// Lower hull
for (auto& p : pts) {
while (hull.size() >= 2 &&
cross(hull[hull.size()-2], hull[hull.size()-1], p) <= 0)
hull.pop_back();
hull.push_back(p);
}
// Upper hull
int lower_sz = hull.size();
for (int i = n - 2; i >= 0; i--) {
while ((int)hull.size() > lower_sz &&
cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
hull.pop_back();
hull.push_back(pts[i]);
}
hull.pop_back(); // remove duplicate of first point
return hull;
}Convex hull -- Explained version
cpp
vector<P> convex_hull(vector<P> pts) {
int n = pts.size();
if (n < 2) return pts;
// Sort lexicographically by (x, y). This lets us sweep
// left-to-right for lower hull, right-to-left for upper.
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
n = pts.size();
if (n < 2) return pts;
vector<P> hull;
// --- Lower hull ---
// Sweep left to right. Maintain a stack (hull) such that
// consecutive triples always turn strictly left (CCW).
// If cross <= 0 (right turn or collinear), the middle point
// is redundant -- pop it.
for (auto& p : pts) {
while (hull.size() >= 2) {
P a = hull[hull.size() - 2];
P b = hull[hull.size() - 1];
if (cross(a, b, p) <= 0) // not a left turn
hull.pop_back();
else
break;
}
hull.push_back(p);
}
// --- Upper hull ---
// Same logic, sweep right to left. lower_sz marks where the
// lower hull ends so we don't pop into it.
int lower_sz = hull.size();
for (int i = n - 2; i >= 0; i--) {
while ((int)hull.size() > lower_sz) {
P a = hull[hull.size() - 2];
P b = hull[hull.size() - 1];
if (cross(a, b, pts[i]) <= 0)
hull.pop_back();
else
break;
}
hull.push_back(pts[i]);
}
hull.pop_back(); // first point duplicated at end
return hull;
}Point-in-convex-polygon --
cpp
// Assumes hull is CCW, hull[0] is the "pivot" (e.g. leftmost-bottom).
// Returns: 1 = strictly inside, 0 = on boundary, -1 = outside.
int in_convex_polygon(const vector<P>& hull, P q) {
int n = hull.size();
if (n < 3) return -1;
// Check if q is on the correct side of the first and last edges.
if (cross(hull[0], hull[1], q) < 0) return -1;
if (cross(hull[0], hull[n-1], q) > 0) return -1;
// Binary search for the sector containing q.
int lo = 1, hi = n - 1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (cross(hull[0], hull[mid], q) >= 0)
lo = mid;
else
hi = mid;
}
ll c = cross(hull[lo], hull[hi], q);
if (c > 0) return 1; // strictly inside
if (c == 0) { // on edge hull[lo]->hull[hi]
// Check if on boundary of the hull
return 0;
}
return -1;
}Point-in-polygon (general, simple polygon) -- Ray casting
Ray Casting (point-in-polygon):
+--------+ * = query point
| * | --> = ray along +x
| (1 crossing = inside)
+--------+------>
* +--------+
| (0 crossings = outside)
+--------+------>
Odd crossings = inside, Even crossings = outsidecpp
// Works for any simple polygon (convex or concave).
// Returns: 1 = inside, 0 = on boundary, -1 = outside.
// Uses ray casting along +x direction.
int point_in_polygon(const vector<P>& poly, P q) {
int n = poly.size(), crossings = 0;
for (int i = 0; i < n; i++) {
P a = poly[i], b = poly[(i + 1) % n];
// Check if q lies on segment a-b.
if (cross(a, b, q) == 0 &&
dot(a - q, b - q) <= 0)
return 0; // on boundary
// Count ray crossings.
if ((a.y <= q.y) != (b.y <= q.y)) {
// x-coordinate of intersection of edge with y = q.y
// Multiply both sides by (b.y-a.y) to stay in integers.
ll num = (ll)(q.y - a.y) * (b.x - a.x);
ll den = b.y - a.y;
// intersection x = a.x + num/den
// q.x < intersection iff q.x * den < a.x * den + num
// (careful with sign of den)
ll lhs = (q.x - a.x) * den;
if (den > 0 ? lhs < num : lhs > num)
crossings++;
}
}
return crossings % 2 == 1 ? 1 : -1;
}Polygon area -- Shoelace formula
cpp
// Returns TWICE the signed area (positive if CCW).
ll twice_area(const vector<P>& poly) {
ll area = 0;
int n = poly.size();
for (int i = 0; i < n; i++)
area += cross(poly[i], poly[(i + 1) % n]);
return area;
}Operations Reference
| Operation | Time | Space | Notes |
|---|---|---|---|
| Cross product | Core primitive | ||
| Orientation test | Sign of cross product | ||
| Convex hull (monotone) | Dominated by sort | ||
| Point in convex polygon | Binary search on sectors | ||
| Point in simple polygon | Ray casting | ||
| Polygon area (shoelace) | Sum of cross products / 2 | ||
| Segment intersection | Cross product checks |
Problem Patterns & Tricks
Pattern 1: "Convex Hull + Property Query"
Build hull, then answer queries (farthest point, width, diameter).
cpp
auto hull = convex_hull(pts);
// Diameter via rotating calipers on hull -- O(n)CF Examples: 166B, 1290A
Pattern 2: "Online Convex Hull Trick (geometry version)"
Maintain a convex hull as points are inserted. Use a set<P> with tangent-line queries. Not to be confused with the DP convex hull trick.
CF Examples: 70D (Protecting Sheep)
Pattern 3: "Area / Perimeter via Shoelace"
Given polygon vertices in order, compute area or perimeter.
cpp
ll area2 = abs(twice_area(poly));
// area = area2 / 2 (print as integer or with .5)CF Examples: CSES 2191 (Polygon Area)
Pattern 4: "Point-in-Polygon Batch"
Given a polygon and many query points, preprocess convex hull for
CF Examples: CSES 2192 (Point in Polygon)
Pattern 5: "Convex Hull to Reduce Search Space"
Only hull points can be extremal in any direction. Reduce
cpp
auto hull = convex_hull(pts);
// Now work with hull.size() points (often much smaller)CF Examples: 1374E2
Pattern 6: "Half-Plane Intersection"
Intersect a set of half-planes (each defined by a line and a side). Sort by angle, use a deque. Result is a convex polygon.
CF Examples: 1903F
Contest Cheat Sheet
+================================================================+
| GEOMETRY BASICS CHEAT SHEET |
+================================================================+
| CROSS PRODUCT: |
| cross(O,A,B) = (A-O) x (B-O) |
| > 0: CCW (left turn) == 0: collinear < 0: CW (right turn) |
+----------------------------------------------------------------+
| CONVEX HULL (Andrew's Monotone Chain): |
| 1. Sort by (x, y) |
| 2. Lower hull: sweep L->R, pop while cross <= 0 |
| 3. Upper hull: sweep R->L, pop while cross <= 0 |
| Time: O(n log n) Space: O(n) |
+----------------------------------------------------------------+
| POINT IN CONVEX POLYGON: O(log n) |
| Binary search on angular sectors from hull[0] |
+----------------------------------------------------------------+
| POINT IN SIMPLE POLYGON: O(n) |
| Ray casting: count crossings of +x ray with edges |
+----------------------------------------------------------------+
| POLYGON AREA: sum of cross(poly[i], poly[i+1]) / 2 |
+----------------------------------------------------------------+
| WATCH OUT: |
| - Use long long for cross products (coords up to 10^9) |
| - Collinear points: decide include or exclude on hull |
| - Degenerate cases: all collinear, n <= 2 |
+================================================================+Gotchas & Debugging
Gotcha 1: Integer overflow in cross product
Coordinates up to long long (__int128 or restructure the comparison.
Gotcha 2: Floating-point epsilon hell
If you must use double, never compare with ==. Use:
cpp
const double EPS = 1e-9;
bool eq(double a, double b) { return fabs(a - b) < EPS; }But prefer integer arithmetic. Cross products, orientation tests, and area computations are all exact with integers.
Gotcha 3: Collinear points on hull
cross <= 0 in the pop condition excludes collinear points from the hull. If you need them (e.g., count lattice points on boundary), change to cross < 0. But then the upper/lower hull join needs care to avoid duplicates.
Gotcha 4: Convex hull with all points collinear
If all points are collinear, the hull degenerates to a line segment (2 points). Make sure your code handles hull.size() < 3 before doing polygon operations.
Gotcha 5: Polygon vertex order
Shoelace gives signed area. If vertices are CW, the area is negative. Always use abs() or ensure CCW order first.
Gotcha 6: "On boundary" edge cases in point-in-polygon
Ray casting can miscount when the ray passes exactly through a vertex. The standard fix: count a vertex as "crossed" only if it is the lower endpoint of its edge (the a.y <= q.y != b.y <= q.y trick in the code above).
Mental Traps
Trap: "I know what a cross product is from linear algebra." The linear algebra cross product is 3D and produces a vector. The 2D geometry cross product is the z-component of that vector -- a scalar. The geometric interpretation (signed area, turn direction) is what matters in CP, not the formula. Knowing the formula without the geometric interpretation is how you apply it correctly on examples but misapply it on non-obvious cases.
Trap: "Geometry problems are just implementation." Geometry problems are implementation-heavy, but the hard part is knowing which geometric primitive you need and setting up the coordinate system correctly. Many WAs come from using the right primitive incorrectly (wrong orientation, wrong sign) rather than from buggy code.
Trap: "Epsilon comparison makes floating-point safe." Epsilon helps but doesn't fix the fundamental problem. If you have a chain of floating-point operations, each introducing
Trap: Thinking polygon orientation doesn't matter. Whether a polygon's vertices are listed clockwise or counter-clockwise affects the sign of the shoelace formula, the direction of normals, and many other things. Problems often specify CW or CCW output. Don't assume -- check with the shoelace sign, and add a reversal if needed.
Debug checklist
[ ] Coordinates fit in long long? (max |coord| * max |coord| < 9e18)
[ ] Sorted points before hull construction?
[ ] Handled n=0, n=1, n=2 edge cases?
[ ] Hull returned in expected order (CCW vs CW)?
[ ] Polygon area using cross(poly[i], poly[(i+1)%n]), not poly[i+1]?
[ ] For point-in-polygon, polygon is simple (no self-intersections)?Self-Test
Before moving on, verify you can do these without opening the reference sections above:
- [ ] Write the 2D cross product from scratch -- both the three-argument version
cross(O, A, B)that computes the signed area of triangle OAB, and the two-argument versioncross(A, B)where A and B are vectors. - [ ] Determine orientation of three points using only your cross product function: given A=(0,0), B=(3,0), C=(1,2), which direction is the turn? Verify by computing.
- [ ] Identify the overflow threshold: at what coordinate magnitude does the cross product overflow
long long? (Hint: aroundper coordinate -- is safe, but multiplying two cross products may not be.) - [ ] State when to use integer vs. floating-point in a geometry problem, in one sentence each. Know the decision tree.
- [ ] Write the epsilon comparison function from memory (
eq(a, b)usingfabsandEPS). Explain why a fixed epsilon is dangerous for accumulated computations. - [ ] Trace Andrew's monotone chain on 4-5 points by hand -- push, pop, and verify the invariant at each step.
- [ ] Explain ray casting for point-in-polygon: why does odd/even crossing count determine inside/outside? What's the vertex edge case?
Practice Problems
| # | Problem | Source | Difficulty | Key Idea |
|---|---|---|---|---|
| 1 | Polygon Area | CSES 2191 | Easy | Shoelace formula |
| 2 | Point in Polygon | CSES 2192 | Easy | Ray casting |
| 3 | Convex Hull | CSES 2195 | Easy | Andrew's monotone chain |
| 4 | Line Segment Intersection | CSES 2190 | Medium | Cross product orientation |
| 5 | Andrew and Stones | CF 70D | Medium | Online convex hull maintenance |
| 6 | Polygon | CF 166B | Medium | Convex hull containment |
| 7 | Farthest Pair | CF 1290A | Medium | Hull + rotating calipers |
| 8 | Minimum Bounding Rectangle | Kattis | Hard | Hull + rotating calipers |
| 9 | Half-plane Intersection | CF 1903F | Hard | Sort by angle, deque sweep |
| 10 | Beautiful Pair | CF 1270F | Hard | Geometry + divide and conquer |
Further Reading
- cp-algorithms: Convex Hull (Andrew's monotone chain)
- cp-algorithms: Point in Polygon
- CF Blog: Geometry for Competitive Programming (Al.Cash)
- USACO Guide: Convex Hull
- Topcoder: Geometry Concepts
- Victor Lecomte, Handbook of Geometry for Competitive Programmers
Cross-references within this notebook:
- Sorting and Custom Comparators -- needed for hull sort
- Binary Search -- used in
point-in-convex-polygon - Coordinate Compression -- sometimes combined with geometry
The Aha Moment
Every geometric relationship -- left/right of a line, inside/outside a polygon, clockwise or counter-clockwise -- reduces to checking the sign of a cross product. Once you internalize that
cross(B-A, C-A) > 0means "C is to the left of the directed line A-->B," the rest of computational geometry is just clever reuse of that single operation.
Pattern Fingerprint
Fingerprint: "determine relative position of points/lines" -> cross product sign test
Fingerprint: "is point inside a simple polygon?" -> ray casting (odd/even crossing count)
Fingerprint: "area of polygon given vertices" -> shoelace formula via cumulative cross products
Rating Progression
| CF Rating | What to Master |
|---|---|
| 1200 | Implement Point struct with +, -, cross, dot. Compute triangle area via cross product. Solve basic "which side of the line" problems. |
| 1500 | Orientation test (CW/CCW/collinear). Segment-segment intersection. Point-in-convex-polygon via binary search on cross products. |
| 1800 | Ray-casting for arbitrary simple polygons. Signed area / shoelace formula. Handling collinear and degenerate cases robustly. |
| 2100 | Epsilon-free exact integer arithmetic for all primitives. Reduction of geometric problems to cross-product queries. Combining geometry with sweep-line or divide-and-conquer. |
Before You Code Checklist
- [ ] Am I using
long long(or__int128) to avoid overflow in cross products when coordinates reach? - [ ] Have I defined a consistent orientation convention (e.g., CCW = positive cross product) and stuck with it everywhere?
- [ ] Does my segment intersection handle the collinear/endpoint-touching cases correctly?
- [ ] For point-in-polygon, have I decided how to treat points exactly on the boundary (and documented it)?
- [ ] Did I avoid floating-point comparisons by keeping everything in integer cross products where possible?
What Would You Do If...?
Scenario 1: The problem says "determine if point P is strictly inside polygon Q," but your ray-casting says a point on the edge is inside.
Answer: Ray-casting counts boundary crossings. A point exactly on an edge can produce an ambiguous count. Add explicit on-segment checks before the ray cast: if P lies on any edge, report "on boundary" separately from "inside."
Scenario 2: Two segments share a common endpoint and your intersection code reports them as non-intersecting.
Answer: Your intersection likely uses strict inequality (
cross > 0instead ofcross >= 0). For endpoint-touching, the cross product is exactly zero. Change the check to<=/>=and add a bounding-box containment test for the collinear sub-case.
Scenario 3: Your solution passes all small tests but gets WA on a test where all points are collinear.
Answer: When all points are collinear, cross products are all zero. Many geometry routines (polygon area, orientation sort) degenerate silently. Handle the collinear case as a special branch: the "polygon" is a segment, the "area" is zero, and the "hull" is just the two extreme points.
The Mistake That Teaches
I once solved a "point in triangle" problem by checking whether the three cross products cross(AB, AP), cross(BC, BP), cross(CA, CP) all had the same sign. It passed the examples beautifully. Then test 17 gave WA.
I stared at the code for an hour. The logic was textbook-correct -- or so I thought. The bug? My coordinates were up to int. I was storing the cross product result in int instead of long long. The sign was flipping on overflow, silently turning a "left" into a "right."
After switching to long long, the solution went AC. Lesson learned: in geometry, overflow is the #1 silent killer. Always compute cross products in a type that can hold
Debug This
Bug 1: This cross product function sometimes returns wrong signs for large coordinates.
cpp
struct Point { int x, y; };
int cross(Point O, Point A, Point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}What's the bug?
The return type and intermediate arithmetic use int. When coordinates are up to int. Fix: use long long for the return type and cast before multiplication:
cpp
long long cross(Point O, Point A, Point B) {
return (long long)(A.x - O.x) * (B.y - O.y)
- (long long)(A.y - O.y) * (B.x - O.x);
}Bug 2: This point-in-polygon (ray casting) miscounts for some polygons.
cpp
bool inPolygon(vector<Point>& poly, Point p) {
int n = poly.size(), cnt = 0;
for (int i = 0; i < n; i++) {
Point a = poly[i], b = poly[(i + 1) % n];
if (a.y > b.y) swap(a, b);
if (p.y > a.y && p.y <= b.y) {
long long cp = cross(a, b, p);
if (cp > 0) cnt++;
}
}
return cnt % 2 == 1;
}What's the bug?
After swap(a, b) to ensure a.y <= b.y, the orientation of edge (a, b) may have flipped relative to the polygon's winding order. The cross-product sign test cp > 0 was calibrated for the original winding direction. When the swap occurs, the crossing test inverts. Fix: track whether a swap happened and negate the cross-product condition accordingly, or avoid swapping and instead use the original vertex order with an appropriate range check on p.y.
Bug 3: This segment intersection test says parallel overlapping segments don't intersect.
cpp
bool onSegment(Point p, Point a, Point b) {
return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x)
&& min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y);
}
bool segmentsIntersect(Point a, Point b, Point c, Point d) {
long long d1 = cross(c, d, a), d2 = cross(c, d, b);
long long d3 = cross(a, b, c), d4 = cross(a, b, d);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))
return true;
if (d1 == 0 && onSegment(a, c, d)) return true;
if (d2 == 0 && onSegment(b, c, d)) return true;
return false;
}What's the bug?
The function only checks collinear cases for points a and b on segment cd. It never checks whether c or d lie on segment ab. When d3 == 0 (point c is collinear with ab) or d4 == 0 (point d is collinear with ab), those cases are missed. Add:
cpp
if (d3 == 0 && onSegment(c, a, b)) return true;
if (d4 == 0 && onSegment(d, a, b)) return true;Historical Origin
The cross product's use as an orientation test dates back to computational geometry's formalization in the 1970s by Shamos and Hoey. The shoelace formula for polygon area is attributed to the surveyor Albrecht Ludwig Friedrich Meister (1769), making it one of the oldest algorithmic geometry results still used in competitive programming.
Mnemonic Anchor
"When in doubt, cross it out" — every geometric query starts with a cross product. Or, in nautical form: positive means port (left), negative means starboard (right), zero means dead ahead.
Common Mistakes
- Integer overflow in cross product. With coordinates up to
, the cross product can reach — use long long(or__int128if you then multiply two cross products together). - Wrong orientation convention. Mixing up CW vs CCW silently flips signs across the whole solution. Pick one rule (this file uses cross > 0 = CCW) and stick to it everywhere.
- Collinear points not handled. Many geometry algorithms break when three consecutive points are collinear. Always decide what to do with cross = 0.
- Floating-point comparison with
==. Never compare doubles with==. Useabs(a - b) < EPS— and prefer integers in the first place.
Recap and Cross-Links
| Concept | Link |
|---|---|
| Sorting | 03-sorting-and-searching |
| Convex Hull (full file) | 02-convex-hull |
| Point-in-polygon (full file) | 05-point-in-polygon |
| Rotating Calipers | 03-rotating-calipers |
| Half-Plane Intersection | 04-half-plane-intersection |
| Floating-point safety net | 11-floating-point-gotchas |
| Practice | Ladder - Mixed |