⚙️AlgorithmIntermediate

Basic Geometry - Lines and Segments

Key Points

  • •
    A line can be represented by two points, a point with a direction vector, or the general form ax + by + c = 0, and these forms are interconvertible.
  • •
    The orientation test using the 2D cross product tells you if three points make a left turn, right turn, or are collinear.
  • •
    Two lines intersect at a single point unless they are parallel (no solution) or coincident (infinitely many solutions); use Cramer's rule to solve ax + by + c = 0 pairs.
  • •
    Two segments intersect if their endpoints lie on opposite sides of the other segment's supporting line or they are collinear with overlapping projections.
  • •
    The perpendicular foot of a point onto a line is the projection of the point onto the line's direction vector.
  • •
    Point-to-line distance is the absolute value of ax0 + by0 + c divided by the length of the normal vector sqrt( + ).
  • •
    Use an epsilon for floating-point comparisons or stick to 64-bit integers for orientation when inputs are integers.
  • •
    All individual geometric predicates and constructions discussed here run in O(1) time and O(1) space.

Prerequisites

  • →Vectors and 2D coordinate geometry — Understanding points, vectors, and coordinate systems is essential for representing lines and computing dot/cross products.
  • →Dot and cross products — Orientation, projection, and many distance formulas rely on dot and cross product properties.
  • →Basic linear equations — Line intersections are solved by a 2×2 linear system using determinants (Cramer's rule).
  • →Floating-point arithmetic and precision — Geometric predicates often require epsilon-based comparisons to avoid instability.
  • →Absolute value and square root — Distances and lengths use |·| and sqrt to compute magnitudes.

Detailed Explanation

Tap terms for definitions

01Overview

Basic planar geometry for lines and segments underpins many competitive programming problems, from polygon algorithms to ray casting, visibility, and sweeping. At its heart are a few robust representations of lines, plus a small toolbox of operations: orientation (via the cross product), line-line intersection (via solving linear equations), segment intersection (combining orientation and interval overlap), and projection-based computations like the perpendicular foot and distances. A line can be described with two points, a point plus a direction vector, or the general equation ax + by + c = 0; each representation is useful in a different context: vector forms for projection and distances, and ax + by + c = 0 for algebraic solving and normalization. Segment intersection requires extra care: unlike infinite lines, segments are bounded, so after solving for where lines meet, you must also verify that the intersection parameter lies within [0,1] along both segments, and handle collinearity and overlapping edges. For distances and perpendicular feet, vector projection formulas give clean, numerically stable methods. With careful use of epsilon thresholds for floating-point data and integer-based predicates for integral inputs, you can write short, reliable routines that scale to typical problem constraints. The ideas presented here are fundamental building blocks; mastering them will make many 1400–1800 CF problems feel natural.

02Intuition & Analogies

Imagine a straight, infinitely long road: that is a line. You can describe where the road goes by picking two landmarks it passes through, or by giving a starting point and the direction the road heads. Another way is to think of a rule like ax + by + c = 0 that every point on the road obeys—like saying all points whose coordinates satisfy a simple balance. Now imagine two such roads on a map. If they are not parallel, they cross at exactly one intersection. If they head in exactly the same direction and line up, they overlap entirely; if they are parallel but offset, they never meet. For line segments, think of two finite sticks instead of infinite roads. Even if the supporting roads cross somewhere, the sticks only touch if that crossing lies within both stick lengths. A simple hand rule helps: stand at one endpoint of a stick, look along the stick, and check on which side the other stick’s endpoints lie—if they’re on opposite sides, the sticks cross. Collinear sticks are like two rulers on the same line: they overlap if their projections onto the x and y axes overlap. For dropping a perpendicular from a point to a road, picture shining a flashlight straight down to the road—the bright spot is the perpendicular foot. Measuring the shortest distance from the point to the road is just measuring to that bright spot. All these tasks become small vector games: combining arrows (vectors), checking turns (cross product), and projecting shadows (dot product).

03Formal Definition

A 2D line L can be represented in three equivalent ways: (1) two distinct points P1 = (x1, y1) and P2 = (x2, y2) with P1 ≠ P2; (2) a point P0 = (x0, y0) and a nonzero direction vector d = (dx, dy), defining the parametric form L(t) = P0 + t d for t ; (3) general form a x + b y + with (a, b) ≠ (0, 0), unique up to nonzero scaling. Conversions: given P1, P2, choose − y2, − x1, y2 − x2 y1. The orientation of ordered triple (A, B, C) is ((B − A) (C − A)), where the 2D cross product returns a scalar (x1 y2 − y1 x2). indicates a counterclockwise turn, < 0 clockwise, collinear. Two lines a1 x + b1 y + c1 = 0 and a2 x + b2 y + c2 = 0 intersect uniquely iff their determinant b2 − a2 b1 ≠ 0; the intersection solves the 2×2 system. A closed segment is S = { A + t (B − A) | t [0, 1] }. Segments S1 = and S2 = intersect if and only if orientations o1 = (A, B, C) and o2 = (A, B, D) have opposite signs, and o3 = (C, D, A) and o4 = (C, D, B) have opposite signs; collinear cases require checking interval overlap. The perpendicular projection (foot) of point P onto line through A and B is (B − A) with t = . The point-to-line distance is \frac{|a x_{0} + b y_{0} + c|}{}.

04When to Use

Use line and segment primitives whenever you need to: detect if paths cross (e.g., segment intersection in sweep line, simple polygon checks), compute distances (e.g., nearest obstacle, snapping positions to roads), construct auxiliary geometry (e.g., reflect a point across a mirror line, drop perpendiculars), or solve linear constraints (e.g., intersection of borders, clipping). Choose representations based on operation: use parametric (point + direction) for projections, feet, and distances; use general form ax + by + c = 0 for algebraic intersection and distance to line; use two-point form when inputs are given as endpoints and for segment tests. If your inputs are integers and you only need predicates (like orientation, on-segment), prefer exact integer arithmetic to avoid floating error. If you need coordinates of intersections or feet, doubles or long doubles are appropriate, with an epsilon for comparisons. In problems at CF 1400–1800, typical uses include: validating polygon simplicity, ray-segment intersections in point-in-polygon, finding the first collision in motion along a direction, computing minimal distances from a point to walls, and determining whether a path crosses a forbidden segment.

⚠️Common Mistakes

  • Ignoring parallel and coincident lines: when solving two line equations, always check the determinant D; if D = 0, they are parallel or coincident, and naive division causes division by zero or garbage.
  • Missing collinear-overlap cases for segments: the general opposite-sides test fails when all orientations are zero; you must explicitly handle collinearity by checking bounding-box overlap and on-segment conditions.
  • Floating-point equality without epsilon: testing values like t in [0,1] using exact comparisons can fail due to roundoff. Use an epsilon, e.g., t >= -eps and t <= 1 + eps, and treat small magnitudes as zero.
  • Not normalizing or handling near-degenerate direction vectors: projecting onto a zero-length segment (A == B) leads to division by zero; guard for degenerate segments.
  • Overflow with 32-bit ints in cross products: with coordinates up to 10^9, use 64-bit integers for integer predicates; cross products can reach about 10^{18}.
  • Returning an intersection point for overlapping collinear segments: there are infinitely many intersection points. Clearly distinguish: no intersection, unique point, or overlapping segment.
  • Forgetting to clamp projections for point-to-segment distance: the perpendicular foot can lie outside the segment; clamp the parameter t to [0,1] before measuring distance.

Key Formulas

Two-point to general form

Explanation: Given two distinct points, you can build coefficients a, b, c so that every point on the line satisfies ax + by + c = 0. This is a convenient algebraic form for intersection and distance.

Parametric line

Explanation: A line is all points reached by starting at P0 and walking any real multiple t of the direction vector d. This form is ideal for projections and checking parameter ranges on segments.

Orientation via cross product

Explanation: The sign indicates whether C is to the left of AB, right of it, or on it. This is the core predicate for segment intersection tests.

Determinant for line intersection

Explanation: If D = 0, the lines are parallel or coincident; otherwise there is a unique intersection found via Cramer's rule. Always check D before dividing.

Cramer's rule for ax+by+c=0 pairs

Explanation: Solving the system a1 x + b1 y = −c1 and a2 x + b2 y = −c2 yields the intersection coordinates. Use when .

Point-to-line distance

Explanation: Plug the point into the line equation and divide by the normal vector length. This gives the shortest distance from P to the infinite line.

Vector projection

Explanation: This produces the component of u along v. It is the basis for computing a perpendicular foot and point-to-segment distance.

Perpendicular foot on a line

Explanation: The foot F is obtained by moving from A along AB by parameter t equal to the normalized dot product. Clamp t to [0,1] for a segment.

Segment intersection condition

Explanation: Here o1=orient(A,B,C), o2=orient(A,B,D), o3=orient(C,D,A), o4=orient(C,D,B). Strictly negative products indicate proper crossing; zeros require on-segment checks for collinearity.

Distance between two segments

Explanation: If segments touch or cross, the distance is zero. Otherwise, the shortest distance occurs from an endpoint to the other segment.

Complexity Analysis

All the geometric primitives discussed—orientation tests, line-line intersection via Cramer's rule, point-to-line/segment distance, and projection to obtain perpendicular feet—run in O(1) time and O(1) additional space per query, since they involve a constant number of arithmetic operations. In practical problems, you often apply these O(1) routines across many inputs: checking n segment pairs naively costs O(), while using sweep-line or plane sweep can reduce intersection detection to O((n + k) log n), where k is the number of intersections, but the local predicates remain O(1). Numerical stability affects effective performance: choosing double vs. long double changes constant factors but not asymptotic complexity. When inputs are integers, prefer 64-bit integer arithmetic for predicates (orientation, on-segment) to avoid floating-point eps checks; this keeps operations exact and still O(1). Be mindful of degeneracies: guard against zero-length segments and near-parallel lines, which could lead to division by (near-)zero; using an epsilon threshold prevents spurious branches and repeated retries. Memory usage is negligible: each function uses a handful of scalar temporaries and returns a point by value or via reference, staying within O(1) space. For batch computations, the total storage scales with input size (e.g., storing n points uses O(n) space), but the algorithms here do not require additional data structures beyond that.

Code Examples

Core geometry: points, lines, and line-line intersection (Cramer's rule)
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point {
5    double x, y;
6};
7
8struct Line { // a x + b y + c = 0
9    double a, b, c;
10};
11
12const double EPS = 1e-9;
13
14// Basic vector operations using points as vectors from origin
15Point operator+(const Point& A, const Point& B) { return {A.x + B.x, A.y + B.y}; }
16Point operator-(const Point& A, const Point& B) { return {A.x - B.x, A.y - B.y}; }
17Point operator*(const Point& A, double k) { return {A.x * k, A.y * k}; }
18
19// Dot and cross products
20static inline double dot(const Point& u, const Point& v) { return u.x * v.x + u.y * v.y; }
21static inline double cross(const Point& u, const Point& v) { return u.x * v.y - u.y * v.x; }
22
23// Build general-form line from two points
24Line line_from_points(const Point& P1, const Point& P2) {
25    // a = y1 - y2, b = x2 - x1, c = x1*y2 - x2*y1
26    double a = P1.y - P2.y;
27    double b = P2.x - P1.x;
28    double c = P1.x * P2.y - P2.x * P1.y;
29    return {a, b, c};
30}
31
32// Intersect two lines a1 x + b1 y + c1 = 0 and a2 x + b2 y + c2 = 0
33// Returns pair<bool, Point>: bool=false if parallel or coincident (no unique intersection)
34pair<bool, Point> intersect_lines(const Line& L1, const Line& L2) {
35    double a1 = L1.a, b1 = L1.b, c1 = L1.c;
36    double a2 = L2.a, b2 = L2.b, c2 = L2.c;
37    double D = a1 * b2 - a2 * b1; // determinant
38    if (fabs(D) < EPS) return {false, {NAN, NAN}}; // parallel or coincident
39    // Solve a1 x + b1 y = -c1, a2 x + b2 y = -c2
40    double x = (b2 * c1 - b1 * c2) / D;
41    double y = (a1 * c2 - a2 * c1) / D;
42    return {true, {x, y}};
43}
44
45int main() {
46    ios::sync_with_stdio(false);
47    cin.tie(nullptr);
48
49    // Example: intersect lines through P1P2 and P3P4
50    Point P1{0, 0}, P2{4, 4};
51    Point P3{0, 4}, P4{4, 0};
52
53    Line L1 = line_from_points(P1, P2);
54    Line L2 = line_from_points(P3, P4);
55    auto [ok, I] = intersect_lines(L1, L2);
56    if (ok) {
57        cout.setf(std::ios::fixed); cout<<setprecision(6);
58        cout << "Intersection: " << I.x << " " << I.y << "\n"; // Expected (2,2)
59    } else {
60        cout << "No unique intersection (parallel or coincident).\n";
61    }
62    return 0;
63}
64

This program defines a minimal 2D geometry toolkit, converts a line from two points to ax + by + c = 0, and computes the intersection of two lines using Cramer's rule. It detects parallel or coincident lines by checking the determinant against an epsilon.

Time: O(1)Space: O(1)
Robust segment-segment intersection with collinearity and overlap
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point { double x, y; };
5const double EPS = 1e-9;
6
7Point operator+(const Point& a, const Point& b){ return {a.x+b.x, a.y+b.y}; }
8Point operator-(const Point& a, const Point& b){ return {a.x-b.x, a.y-b.y}; }
9Point operator*(const Point& a, double k){ return {a.x*k, a.y*k}; }
10
11double cross(const Point& a, const Point& b){ return a.x*b.y - a.y*b.x; }
12double dot(const Point& a, const Point& b){ return a.x*b.x + a.y*b.y; }
13
14int sgn(double x){ if (x > EPS) return 1; if (x < -EPS) return -1; return 0; }
15
16bool on_segment(const Point& a, const Point& b, const Point& p){
17    // check collinearity and bounding box
18    if (sgn(cross(b-a, p-a)) != 0) return false;
19    double minx = min(a.x, b.x) - EPS, maxx = max(a.x, b.x) + EPS;
20    double miny = min(a.y, b.y) - EPS, maxy = max(a.y, b.y) + EPS;
21    return p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy;
22}
23
24bool segments_intersect(const Point& A, const Point& B, const Point& C, const Point& D){
25    Point AB = B - A, AC = C - A, AD = D - A;
26    Point CD = D - C, CA = A - C, CB = B - C;
27    int o1 = sgn(cross(AB, AC));
28    int o2 = sgn(cross(AB, AD));
29    int o3 = sgn(cross(CD, CA));
30    int o4 = sgn(cross(CD, CB));
31
32    if (o1 == 0 && on_segment(A, B, C)) return true;
33    if (o2 == 0 && on_segment(A, B, D)) return true;
34    if (o3 == 0 && on_segment(C, D, A)) return true;
35    if (o4 == 0 && on_segment(C, D, B)) return true;
36
37    return (o1 * o2 < 0) && (o3 * o4 < 0);
38}
39
40// Optional: compute unique intersection point if it exists and is not overlapping collinear
41pair<bool, Point> segment_intersection_point(const Point& A, const Point& B, const Point& C, const Point& D){
42    // Represent as A + t(B-A) = C + u(D-C)
43    Point r = B - A;
44    Point s = D - C;
45    double rxs = cross(r, s);
46    double q_pxr = cross(C - A, r);
47
48    if (fabs(rxs) < EPS && fabs(q_pxr) < EPS){
49        // Collinear: infinite or none; here we return false to indicate not a unique point
50        return {false, {NAN, NAN}};
51    }
52    if (fabs(rxs) < EPS && fabs(q_pxr) >= EPS){
53        // Parallel and disjoint
54        return {false, {NAN, NAN}};
55    }
56    // t = (C - A) x s / (r x s), u = (C - A) x r / (r x s)
57    double t = cross(C - A, s) / rxs;
58    double u = cross(C - A, r) / rxs;
59    if (t >= -EPS && t <= 1.0 + EPS && u >= -EPS && u <= 1.0 + EPS){
60        Point I = A + r * t;
61        return {true, I};
62    }
63    return {false, {NAN, NAN}};
64}
65
66int main(){
67    ios::sync_with_stdio(false);
68    cin.tie(nullptr);
69
70    // Sample tests
71    Point A{0,0}, B{4,4};
72    Point C{0,4}, D{4,0};
73    cout << (segments_intersect(A,B,C,D) ? "YES\n" : "NO\n"); // YES
74    auto [ok, I] = segment_intersection_point(A,B,C,D);
75    if (ok){ cout.setf(std::ios::fixed); cout<<setprecision(6);
76        cout << I.x << " " << I.y << "\n"; // 2.000000 2.000000
77    } else {
78        cout << "No unique intersection point or no intersection.\n";
79    }
80
81    // Collinear overlapping example
82    Point E{1,1}, F{3,3};
83    cout << (segments_intersect(A,B,E,F) ? "YES\n" : "NO\n"); // YES (overlap)
84    auto [ok2, I2] = segment_intersection_point(A,B,E,F);
85    if (!ok2) cout << "Overlap or none -> not a single point.\n";
86
87    return 0;
88}
89

This code implements the standard segment intersection test using orientation (cross products), including all edge cases: proper crossing, endpoint touching, and collinear overlap. It also provides an optional function to compute the unique intersection point when it exists, using a parametric form and cross products.

Time: O(1)Space: O(1)
Perpendicular foot and distances: point-to-line and point-to-segment
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Point { double x, y; };
5const double EPS = 1e-9;
6
7Point operator+(const Point& a, const Point& b){ return {a.x+b.x, a.y+b.y}; }
8Point operator-(const Point& a, const Point& b){ return {a.x-b.x, a.y-b.y}; }
9Point operator*(const Point& a, double k){ return {a.x*k, a.y*k}; }
10
11double dot(const Point& a, const Point& b){ return a.x*b.x + a.y*b.y; }
12double cross(const Point& a, const Point& b){ return a.x*b.y - a.y*b.x; }
13
14double norm2(const Point& a){ return dot(a,a); }
15double norm(const Point& a){ return sqrt(norm2(a)); }
16
17// Foot of perpendicular from P onto the infinite line AB
18Point foot_on_line(const Point& A, const Point& B, const Point& P){
19    Point AB = B - A;
20    double ab2 = norm2(AB);
21    if (ab2 < EPS) return A; // degenerate: return A
22    double t = dot(P - A, AB) / ab2;
23    return A + AB * t;
24}
25
26// Distance from point P to infinite line AB
27double distance_point_line(const Point& A, const Point& B, const Point& P){
28    Point F = foot_on_line(A, B, P);
29    return norm(P - F);
30}
31
32// Distance from point P to segment AB (clamped projection)
33double distance_point_segment(const Point& A, const Point& B, const Point& P){
34    Point AB = B - A;
35    double ab2 = norm2(AB);
36    if (ab2 < EPS) return norm(P - A); // A==B
37    double t = dot(P - A, AB) / ab2;
38    t = max(0.0, min(1.0, t));
39    Point F = A + AB * t;
40    return norm(P - F);
41}
42
43int main(){
44    ios::sync_with_stdio(false);
45    cin.tie(nullptr);
46
47    Point A{0,0}, B{4,0}, P{1,3};
48    Point F = foot_on_line(A, B, P);
49    cout.setf(std::ios::fixed); cout<<setprecision(6);
50    cout << "Foot: " << F.x << " " << F.y << "\n"; // Foot onto x-axis: (1,0)
51    cout << "dist(P,line AB) = " << distance_point_line(A,B,P) << "\n"; // ~3.0
52
53    Point C{5,0};
54    cout << "dist(P,segment BC) = " << distance_point_segment(B,C,P) << "\n"; // distance to (4,0)-(5,0)
55
56    return 0;
57}
58

This program computes the perpendicular foot of a point to an infinite line using vector projection, then uses it to compute distances to a line and to a segment (with clamping). Degenerate segments are handled by falling back to point distance.

Time: O(1)Space: O(1)