Geometry Recipes

Quick Revisit
USE WHEN: geometry is a subtask and you need a copy-paste formula (distance, intersection, area)
INVARIANT: cross product for orientation, dot product for projection — never compare raw angles
TIME: O(1) per primitive operation | SPACE: O(1)
CLASSIC BUG: wrong sign convention on cross product — (A→B)×(A→C) > 0 means CCW (left turn)
PRACTICE: 08-ladder-mixed

A quick-reference cookbook of compact geometry subroutines. Each one: a two-line explanation, the math, and a copy-paste C++ function. For when geometry is a subtask of a non-geometry problem and you need the formula fast.

Difficulty: [Intermediate]Prerequisites: Geometry Basics

Shared Setup

All functions below assume this long double-based header. Each recipe section is also tagged with one of two markers:

[INT-OK] — the operation can be performed exactly with long long integer coordinates. Replace ld with ll, drop the EPS, and keep cross/dot as integers. Recommended whenever inputs are integer.
[FLT-ONLY] — the operation produces non-integer outputs (square roots, divisions that don't simplify, trig). It must use floating point and is sensitive to EPS choice. Read 11-floating-point-gotchas.md before using these in a tight problem.

cpp

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld EPS = 1e-9;

struct P {
    ld x, y;
    P operator-(P o) const { return {x-o.x, y-o.y}; }
    P operator+(P o) const { return {x+o.x, y+o.y}; }
    P operator*(ld t) const { return {x*t, y*t}; }
    ld dot(P o) const { return x*o.x + y*o.y; }
    ld cross(P o) const { return x*o.y - y*o.x; }
    ld norm() const { return sqrt(x*x + y*y); }   // FLT-ONLY: prefer norm2 when comparing
    ld norm2() const { return x*x + y*y; }        // INT-OK with `ll`
};

1. Point-to-Line Distance — [FLT-ONLY]

Shortest distance from point $P$ to the infinite line through $A$ and $B$ . Uses the fact that $| \vec{A P} \times \vec{A B} | / | \vec{A B} |$ gives the perpendicular distance.

cpp

ld point_line_dist(P a, P b, P p) {
    return abs((p-a).cross(b-a)) / (b-a).norm();
}

2. Point-to-Segment Distance — [FLT-ONLY]

Like point-to-line, but clamped to the segment $[A, B]$ . Project $P$ onto the line; if the projection falls outside the segment, use the nearer endpoint.

cpp

ld point_seg_dist(P a, P b, P p) {
    if ((b-a).dot(p-a) < EPS) return (p-a).norm();
    if ((a-b).dot(p-b) < EPS) return (p-b).norm();
    return point_line_dist(a, b, p);
}

3. Segment-Segment Intersection — [INT-OK for proper-crossing test, FLT-ONLY for the intersection point]

Do segments $[A, B]$ and $[C, D]$ intersect? Checks that $C$ and $D$ are on opposite sides of line $A B$ , and vice versa. Returns the intersection point when it exists.

Visual: Line Intersection via Cross Products

  y
  4 |  B(1,4)         D(5,4)
    |   \              /
  3 |    \            /
    |     \    P    /     Segment AB and segment CD,
  2 |      \  (3,2)/      crossing at P = (3, 2).
    |       \    /
  1 |    A(2,0)C(4,1)     (not to scale — schematic)
  0 +--+--+--+--+--+---> x

  cross(A,B,C): is C left/right of line AB?
  cross(A,B,D): is D left/right of line AB?
  If the two signs differ, C and D are on opposite sides of AB —
  same test from CD's frame confirms the proper crossing.

  Compute intersection (when both straddling tests pass):
    t = cross(C-A, D-C) / cross(B-A, D-C)
    P = A + t*(B - A)

Parallel and collinear cases. When cross(B-A, D-C) == 0 the lines are parallel; the formula above divides by zero. Detect this branch first. If cross(B-A, C-A) == 0 as well, the segments are collinear — reduce to the 1D overlap test on the projection along their common direction. The recipe below intentionally returns false in those cases; for full collinear-overlap output you need the bounding-box check from 01-geometry-basics § segment intersection.

cpp

// Returns {true, intersection_point} or {false, {0,0}}
pair<bool, P> seg_seg_intersect(P a, P b, P c, P d) {
    ld d1 = (b-a).cross(c-a), d2 = (b-a).cross(d-a);
    ld d3 = (d-c).cross(a-c), d4 = (d-c).cross(b-c);
    if (((d1 > EPS && d2 < -EPS) || (d1 < -EPS && d2 > EPS)) &&
        ((d3 > EPS && d4 < -EPS) || (d3 < -EPS && d4 > EPS))) {
        ld t = d3 / (d3 - d4);
        return {true, a + (b-a)*t};
    }
    // collinear / endpoint cases: add overlap checks if needed
    return {false, {0, 0}};
}

4. Circle-Line Intersection — [FLT-ONLY]

A line through $A$ and $B$ intersects a circle (center $C$ , radius $r$ ) in 0, 1, or 2 points. Project $C$ onto the line, then offset along the line by $\sqrt{r^{2} - d^{2}}$ where $d$ is the distance from $C$ to the line.

cpp

vector<P> circle_line(P c, ld r, P a, P b) {
    P ab = b - a;
    ld d = (c-a).cross(ab) / ab.norm();
    if (abs(d) > r + EPS) return {};
    P proj = a + ab * ((c-a).dot(ab) / ab.dot(ab));
    ld h = sqrt(max((ld)0, r*r - d*d));
    P offset = {ab.x/ab.norm()*h, ab.y/ab.norm()*h};
    if (h < EPS) return {proj};
    return {proj - offset, proj + offset};
}

5. Circle-Circle Intersection — [FLT-ONLY]

Two circles (centers $C_{1}, C_{2}$ , radii $r_{1}, r_{2}$ ) intersect when $| r_{1} - r_{2} | \leq d \leq r_{1} + r_{2}$ , where $d$ is the center distance. Find the intersection points via the radical line.

cpp

vector<P> circle_circle(P c1, ld r1, P c2, ld r2) {
    ld d = (c2-c1).norm();
    if (d > r1+r2+EPS || d < abs(r1-r2)-EPS) return {};
    ld a = (r1*r1 - r2*r2 + d*d) / (2*d);
    ld h = sqrt(max((ld)0, r1*r1 - a*a));
    P mid = c1 + (c2-c1)*(a/d);
    P perp = {-(c2-c1).y/d*h, (c2-c1).x/d*h};
    if (h < EPS) return {mid};
    return {mid + perp, mid - perp};
}

6. Tangent Lines to a Circle from External Point — [FLT-ONLY]

From point $P$ outside circle $(C, r)$ , there are exactly two tangent lines. Each tangent touches the circle at one point. The tangent length is $\sqrt{| P C |^{2} - r^{2}}$ .

cpp

vector<P> tangent_points(P c, ld r, P p) {
    ld d2 = (p-c).norm2(), r2 = r*r;
    if (d2 < r2 - EPS) return {}; // inside circle
    ld d = sqrt(d2);
    ld a = r2 / d, b = sqrt(max((ld)0, r2 - a*a));
    P e = (p-c) * (1/d); // unit vector C->P
    P mid = c + e * a;
    P perp = {-e.y * b, e.x * b};
    if (b < EPS) return {mid};
    return {mid + perp, mid - perp};
}

7. Angle Between Vectors — [FLT-ONLY]

The signed angle from vector $\vec{u}$ to vector $\vec{v}$ , counter-clockwise positive. Use atan2 of cross and dot products.

cpp

ld angle_between(P u, P v) {
    return atan2(u.cross(v), u.dot(v));
}

Returns a value in $(- π, π]$ . For the unsigned angle, take abs(...).

8. Rotation by Angle — [FLT-ONLY] (special angles like 90° / 180° / 270° are INT-OK via swap-and-negate)

Rotate point $P$ around the origin by angle $θ$ (radians, counter-clockwise). This is a 2D rotation matrix multiplication.

cpp

P rotate(P p, ld theta) {
    ld c = cos(theta), s = sin(theta);
    return {p.x*c - p.y*s, p.x*s + p.y*c};
}

// Rotate around arbitrary center:
P rotate_around(P p, P center, ld theta) {
    return center + rotate(p - center, theta);
}

9. Reflection Across a Line — [FLT-ONLY in general; INT-OK if line passes through the origin and the "scaling" cancels — verify your specific case]

Reflect point $P$ across the line through $A$ and $B$ . Project $P$ onto the line, then mirror: $P^{'} = 2 \cdot proj - P$ .

cpp

P reflect(P a, P b, P p) {
    P ab = b - a;
    P proj = a + ab * ((p-a).dot(ab) / ab.dot(ab));
    return proj * 2 - p;
}

When Geometry Invades Non-Geometry Problems

Sometimes a problem that looks like graph theory or DP has a geometry subroutine hiding inside:

"Manhattan distance" -- rotate coordinates by 45 deg to convert to Chebyshev distance: $(x, y) \to (x + y, x - y)$ . Now each dimension is independent.
"Maximum/minimum distance" -- often reducible to convex hull + rotating calipers or just brute force on hull vertices.
"Area of intersection" -- typically circle-circle or rectangle overlap. Use the formulas above, don't rederive.
"Angle sweep" -- sort events by atan2, process in angular order. Common in visibility and radar problems.

The recipes above are your avoid-rederiving-under-pressure kit. Code them once, test once, paste forever.

Precision Survival Guide

Situation	Recommendation
Coordinates $\leq 10^{4}$ , answer is integer	Use `long long`, avoid floating point entirely
Coordinates $\leq 10^{9}$ , answer is integer	Use `__int128` for intermediate cross products
Answer requires 6 decimal digits	`long double` with EPS $= 10^{- 9}$
Answer requires 9+ decimal digits	Consider exact arithmetic or careful error analysis
Comparing `atan2` results	Never use `==`; always use EPS comparison
`sqrt` of a value that might be slightly negative	`sqrt(max(0.0L, x))` -- numerical noise can make it $- 10^{- 15}$

Self-Test

Q1. You need the distance from a point to a segment (not an infinite line). What extra check do you need beyond the point-to-line formula?
Answer
Check whether the perpendicular projection of the point onto the line falls within the segment. If it falls outside (dot product test), use the distance to the nearer endpoint instead. The `point_seg_dist` recipe does this with two dot product checks.

Q2. Two circles of radii $r_{1}$ and $r_{2}$ with centers distance $d$ apart. Under what conditions do they have exactly 1, 2, or 0 intersection points?
Answer
0 points: $d > r_1 + r_2$ (too far apart) or $d < |r_1 - r_2|$ (one inside the other). 1 point: $d = r_1 + r_2$ (externally tangent) or $d = |r_1 - r_2|$ (internally tangent). 2 points: $|r_1 - r_2| < d < r_1 + r_2$.

Q3. Why should you avoid computing slopes ( $Δ y / Δ x$ ) for line intersection and use cross products instead?
Answer
Slopes fail for vertical lines ($\Delta x = 0$), require special-case handling, and introduce floating-point division. Cross products work uniformly for all orientations, handle vertical/horizontal lines naturally, and can stay in integer arithmetic when coordinates are integers.

Q4. The Manhattan-to-Chebyshev trick transforms $(x, y) \to (x + y, x - y)$ . When is this useful?
Answer
When the problem involves Manhattan distance ($|x_1-x_2| + |y_1-y_2|$). After the rotation, Manhattan distance becomes Chebyshev distance ($\max(|x_1'-x_2'|, |y_1'-y_2'|)$), which decouples the dimensions. This lets you solve each dimension independently with 1D techniques (sorting, segment trees).

Q5. Why does the circle_line recipe use sqrt(max(0.0L, r*r - d*d)) instead of just sqrt(r*r - d*d)?
Answer
When the line is tangent or nearly tangent, $r^2 - d^2$ can be a tiny negative number (e.g., $-10^{-15}$) due to floating-point rounding. Taking `sqrt` of a negative number gives `NaN`. The `max(0, ...)` clamp prevents this silently.

Practice Problems

Problem	Recipes used
CF 598C -- Nearest Vectors	Angle between vectors, `atan2`
CF 600D -- Area of Two Circles	Circle-circle intersection
CSES -- Point in Polygon	Cross product, point-on-segment
CF 166B -- Polygons	Convex point-in-polygon
Kattis -- Closest Pair	Point-to-point distance
CF 600B -- Queries about Less or Equal	Sorting + binary search (geometry reduction)
Anywhere you see "geometry" as a CF tag	This entire file

Geometry Basics -- the cross product and orientation test underpin every recipe in this file
Convex Hull -- many recipes (farthest pair, tangent queries) operate on convex hulls
Sweep Line Geometry -- event-based processing extends these point/line recipes to bulk operations

Geometry Recipes ​

Shared Setup ​

1. Point-to-Line Distance — [FLT-ONLY] ​

2. Point-to-Segment Distance — [FLT-ONLY] ​

3. Segment-Segment Intersection — [INT-OK for proper-crossing test, FLT-ONLY for the intersection point] ​

Visual: Line Intersection via Cross Products ​

4. Circle-Line Intersection — [FLT-ONLY] ​

5. Circle-Circle Intersection — [FLT-ONLY] ​

6. Tangent Lines to a Circle from External Point — [FLT-ONLY] ​

7. Angle Between Vectors — [FLT-ONLY] ​

8. Rotation by Angle — [FLT-ONLY] (special angles like 90° / 180° / 270° are INT-OK via swap-and-negate) ​

9. Reflection Across a Line — [FLT-ONLY in general; INT-OK if line passes through the origin and the "scaling" cancels — verify your specific case] ​

When Geometry Invades Non-Geometry Problems ​

Precision Survival Guide ​

Self-Test ​

Practice Problems ​

Related Techniques ​