⚙️AlgorithmIntermediate

Basic Geometry - Points and Vectors

Key Points

  • •
    A 2D point can be treated as a vector from the origin, so vector math (addition, scaling, dot, cross) applies directly to points.
  • •
    The dot product a·b equals cos θ and measures how much one vector points in the direction of another, enabling projections and angle computations.
  • •
    The 2D cross product a×b equals sin θ with sign, giving orientation (left/right turn) and twice the signed area of the triangle formed by the vectors.
  • •
    Magnitudes and normalization let you work with unit directions; rotation uses a simple matrix to turn vectors by an angle.
  • •
    Use long long for exact integer geometry (grids, counts) and long double for angles, distances, and rotation to reduce rounding errors.
  • •
    Always compare floating-point numbers with an EPS tolerance instead of == to avoid precision bugs.
  • •
    Orientation tests and segment intersection are classic uses of cross and dot; polygon area uses the shoelace sum of cross products.
  • •
    Each primitive operation is O(1); processing n points (e.g., polygon area) is O(n) time and O(1) extra space.

Prerequisites

  • →Coordinate geometry basics — Understanding Cartesian coordinates and lines is necessary to map algebraic operations to geometric meaning.
  • →Vector algebra — Vector addition, scaling, and linear combinations underlie all point/vector operations.
  • →Trigonometry (radians, sine, cosine) — Angles, rotations, and the relation of dot/cross to sine and cosine rely on trigonometric functions.
  • →Floating-point arithmetic — Knowledge of rounding errors and EPS comparisons is essential for robust geometric code.
  • →C++ operator overloading and structs — Implementing clean geometry primitives benefits from custom types with overloaded operators.
  • →Integer overflow and numeric limits — Choosing between long long and long double and when to widen to 128-bit avoids overflow in cross products.

Detailed Explanation

Tap terms for definitions

01Overview

Basic 2D geometry treats points as ordered pairs (x, y) and vectors as arrows that can be added, scaled, and compared. In competitive programming, this viewpoint turns many geometry problems into clean algebra. Vector addition moves endpoints by stacking arrows; scalar multiplication stretches or shrinks them. Two core operations are the dot product and the 2D cross product: the dot product measures directional similarity (cosine), while the cross product measures oriented area and left/right turns (sine). From these you can compute angles, projections, distances to lines, and detect intersections. Rotation is performed by a small 2×2 matrix that spins vectors around the origin by an angle θ. Because computers use finite precision, careful numeric choices matter: long long gives exact integer arithmetic for grid coordinates, and long double offers extra precision for distances and angles. EPS (a tiny tolerance) is used to compare floating numbers robustly. With these tools, you can build reliable primitives—orientation, segment intersection, projections, and polygon area—that form the backbone of many CF 1400–1800 tasks.

02Intuition & Analogies

Imagine walking on a flat field with a compass. A point (x, y) marks a location on the map; a vector is like an instruction “go 3 steps east and 4 steps north.” Adding vectors is stacking instructions back-to-back: walk 3 east and 4 north, then add 2 east and −1 north—that’s the same as one combined instruction 5 east and 3 north. Scaling a vector doubles or halves your steps, like “go twice as far in the same direction.” Now think about the dot product as how much one instruction follows another’s direction. If you face east and someone says “go northeast,” you partially comply; the dot product is large. If they say “go west,” you disobey your current heading entirely; the dot product becomes negative. That’s why the dot product finds angles and projections—how aligned are we? The 2D cross product acts like a tiny turn-signal. Place your right hand pointing along vector a and sweep toward vector b: if the turn is counterclockwise, the cross is positive; clockwise is negative. Its magnitude equals the area of the parallelogram formed by a and b, so for a triangle it’s half of that. This is why cross products detect orientation (left/right turn) and compute areas (shoelace formula). Rotation is like turning your compass dial by θ degrees while keeping your step length; the rotation matrix rotates every instruction consistently. EPS is your “fuzzy ruler” acknowledging that on a computer, 0.1 + 0.2 might not equal 0.3 exactly—so you allow a tiny slop when comparing results.

03Formal Definition

A 2D point or vector is an element of \(\), represented as \((x, y)\). Vector addition and scalar multiplication are defined component-wise: \((,)+(,)=(+,\,+)\), and for scalar \(\), \((x,y)=( x,\, y)\). The Euclidean norm (magnitude) is \( v = \), and the unit vector (normalization) is \( = v/ v \) for nonzero \(v\). The dot product of vectors \(a=(,)\) and \(b=(,)\) is \(a = a \, b \), where \(\) is the angle between them. The 2D cross product is the scalar \(a = a \, b \), positive if rotating from \(a\) to \(b\) is counterclockwise. A rotation by angle \(\) uses the linear map \(R_(x,y) = (x - y,\; x + y)\). The projection of \(p\) onto line through \(a\) with direction \(d\) is \(a + d\,\). The signed area of triangle \((a,b,c)\) is \(\,((b-a)(c-a))\). In implementation, floating-point comparisons use an \(\) tolerance: treat a value as zero if its absolute value is less than \(\).

04When to Use

  • Orientation and ordering: Use the cross product to determine if three points make a left turn, right turn, or are collinear—vital in convex hulls, polygon monotonicity, and angular sorts.
  • Intersection tests: Combine cross and dot products to check whether two segments intersect (including endpoint touching), or whether a point lies on a segment.
  • Distances and projections: Use the dot product to project a point onto a line, then compute distances to lines or segments—useful in closest pair heuristics, point-in-geometry distance queries, and reflections.
  • Angles and rotations: Compute the angle between vectors using the dot product and norms, or rotate shapes for alignment and coordinate transforms.
  • Areas and centroids: Use cross products to get triangle areas and the shoelace formula for polygon area and centroids, common in computational geometry tasks.
  • Precision-sensitive tasks: Prefer long long when all coordinates are integers and you only need orientation/area (exactness). Switch to long double for distances, angles, and rotations. Always apply EPS when comparing floating values, especially when chaining operations (projection + intersection).

⚠️Common Mistakes

  • Using == with doubles: Floating-point rounding makes direct equality unreliable. Always compare with EPS, e.g., |x| < EPS for zero, or |a-b| < EPS for equality.
  • Mixing integer and floating types carelessly: Doing a cross product in int can overflow if coordinates are up to 1e9; use long long for integer geometry and long double when you need trig or distances.
  • Forgetting to check degenerate cases: Projections onto a zero-length direction, collinear-but-disjoint segments, or nearly parallel lines need special handling (use EPS and guard clauses).
  • Mishandling orientation signs: Remember a×b > 0 means b is to the left of a (CCW turn). Swapping vector order flips the sign.
  • Not clamping when projecting to a segment: Projection onto the supporting line might fall outside the segment. Clamp the parameter t to [0,1] before computing distances to a segment.
  • Angle computations with acos without clamping: Due to rounding, the cosine can be slightly outside [-1,1]. Clamp before calling acos.
  • Using degrees vs radians inconsistently: C++ trig functions use radians. Convert degrees to radians when needed.
  • Ignoring robustness: For polygon area and orientation with integer input, prefer exact integer cross (long long) to avoid tiny nonzero areas from floating error.

Key Formulas

Euclidean Norm

Explanation: This computes the length of a vector. It is the straight-line distance from the origin to (x, y).

Dot Product

Explanation: The dot product equals the product of magnitudes times the cosine of the angle between them. It measures how aligned the vectors are.

2D Cross Product

Explanation: This scalar measures signed area and orientation. Positive means b is to the left of a (counterclockwise), negative means right (clockwise).

Rotation Matrix

Explanation: Multiplying by this matrix rotates a vector by angle θ about the origin. Length is preserved by rotation.

Projection onto a Line

Explanation: This gives the vector from a to the perpendicular foot of p on the line through a in direction d. Add a to get the point of projection.

Orientation Test

Explanation: The sign tells whether turns left, right, or is collinear. Zero (within EPS) means collinear.

Triangle Area

Explanation: Twice the area equals the absolute cross product of the two edge vectors. The sign encodes orientation.

Shoelace Formula

Explanation: Sweep consecutive vertex cross products (with , ). The absolute value gives unsigned area.

Angle via Dot

Explanation: The angle between nonzero vectors is obtained from the cosine. Clamp the value into [-1, 1] before using arccos numerically.

Point-Line Distance

Explanation: Area of the parallelogram divided by base length equals the height, which is the perpendicular distance.

Closest Point on Segment

Explanation: Project p onto the supporting line of segment ab and clamp the parameter to [0,1]. This yields the closest point on the segment to p.

Complexity Analysis

All primitive vector operations—addition, subtraction, scalar multiply/divide, dot, cross, norm, normalization, and rotation—run in O(1) time and O(1) space because they perform a constant number of arithmetic operations. Orientation tests and segment intersection checks are also O(1), as they evaluate a few cross and dot products and constant-time comparisons. When processing collections of points, overall complexity scales with the number of elements. For example, computing the area of a polygon with n vertices using the shoelace formula iterates once over all edges, yielding O(n) time and O(1) extra space. Building projections or distances from one point to every edge in a polygon similarly costs O(n), while pairwise checks among m segments cost O() in the naive approach but each check remains O(1). Space usage is typically O(1) beyond input storage, since geometric primitives do not require additional data structures. Care should be taken with numeric types: using long long for integer-only computations preserves exactness and avoids hidden precision costs; using long double for trigonometry and distances increases numeric stability without changing asymptotic complexity. Robustness features like EPS comparisons add constant overhead but do not affect time or space order. Overall, geometry primitives are computationally light; the main cost arises from how many times you apply them within an algorithm.

Code Examples

Geometry primitives: point/vector struct with dot, cross, norm, normalization, rotation, and EPS-safe comparisons
1#include <bits/stdc++.h>
2using namespace std;
3
4using ld = long double;
5const ld EPS = 1e-12L; // Tolerance for floating comparisons
6
7int sgn(ld x) {
8    if (fabsl(x) < EPS) return 0;
9    return x < 0 ? -1 : 1;
10}
11
12struct Pt {
13    ld x, y;
14    Pt() : x(0), y(0) {}
15    Pt(ld _x, ld _y) : x(_x), y(_y) {}
16
17    // Vector addition and subtraction
18    Pt operator+(const Pt& o) const { return Pt(x + o.x, y + o.y); }
19    Pt operator-(const Pt& o) const { return Pt(x - o.x, y - o.y); }
20
21    // Scalar multiply and divide
22    Pt operator*(ld k) const { return Pt(x * k, y * k); }
23    Pt operator/(ld k) const { return Pt(x / k, y / k); }
24
25    // Dot and cross products
26    ld dot(const Pt& o) const { return x * o.x + y * o.y; }
27    ld cross(const Pt& o) const { return x * o.y - y * o.x; }
28
29    // Squared norm and norm (magnitude)
30    ld norm2() const { return this->dot(*this); }
31    ld norm() const { return sqrtl(norm2()); }
32
33    // Unit vector (normalization); returns (0,0) if vector is ~0
34    Pt unit() const {
35        ld n = norm();
36        if (n < EPS) return Pt(0, 0);
37        return (*this) / n;
38    }
39
40    // Perpendicular vector (rotate by +90 degrees)
41    Pt perp() const { return Pt(-y, x); }
42
43    // Rotate by angle theta (radians) around origin
44    Pt rotate(ld theta) const {
45        ld c = cosl(theta), s = sinl(theta);
46        return Pt(x * c - y * s, x * s + y * c);
47    }
48};
49
50// Angle between two nonzero vectors, in radians, robustly clamped
51ld angle_between(const Pt& a, const Pt& b) {
52    ld na = a.norm(), nb = b.norm();
53    if (na < EPS || nb < EPS) return 0; // undefined; return 0 as a safe default
54    ld cosv = a.dot(b) / (na * nb);
55    cosv = max((ld)-1.0, min((ld)1.0, cosv));
56    return acosl(cosv);
57}
58
59int main() {
60    ios::sync_with_stdio(false);
61    cin.tie(nullptr);
62
63    Pt a(3, 4), b(1, -2);
64
65    // Demonstrate basic operations
66    Pt c = a + b;       // (4, 2)
67    Pt d = a - b;       // (2, 6)
68    Pt e = a * 2;       // (6, 8)
69    ld dot_ab = a.dot(b);   // 3*1 + 4*(-2) = -5
70    ld cross_ab = a.cross(b); // 3*(-2) - 4*1 = -10
71    ld len_a = a.norm();    // 5
72    Pt ua = a.unit();       // (0.6, 0.8)
73
74    // Rotation by 90 degrees (pi/2 radians)
75    Pt r = a.rotate(acosl(-1)/2);
76
77    cout.setf(ios::fixed); cout << setprecision(10);
78    cout << "c=(" << c.x << "," << c.y << ")\n";
79    cout << "d=(" << d.x << "," << d.y << ")\n";
80    cout << "e=(" << e.x << "," << e.y << ")\n";
81    cout << "dot(a,b)=" << dot_ab << ", cross(a,b)=" << cross_ab << "\n";
82    cout << "|a|=" << len_a << ", unit(a)=(" << ua.x << "," << ua.y << ")\n";
83    cout << "a rotated 90 deg = (" << r.x << "," << r.y << ")\n";
84    cout << "angle(a,b) rad = " << angle_between(a,b) << "\n";
85
86    return 0;
87}
88

This program defines a Pt struct for 2D vectors/points using long double. It implements vector arithmetic, dot and cross products, length, unit vector, perpendicular, and rotation. It demonstrates usage and prints results with high precision. The angle_between function clamps the cosine before calling acosl to avoid NaN from rounding. EPS guards normalization and equality-like comparisons.

Time: O(1) per operationSpace: O(1)
Orientation test and robust segment intersection (including endpoints)
1#include <bits/stdc++.h>
2using namespace std;
3
4using ld = long double;
5const ld EPS = 1e-12L;
6
7int sgn(ld x){ if (fabsl(x) < EPS) return 0; return x < 0 ? -1 : 1; }
8
9struct Pt{ ld x,y; Pt(){} Pt(ld X, ld Y):x(X),y(Y){} Pt operator+(const Pt&o)const{return {x+o.x,y+o.y};} Pt operator-(const Pt&o)const{return {x-o.x,y-o.y};} ld cross(const Pt&o)const{return x*o.y - y*o.x;} ld dot(const Pt&o)const{return x*o.x + y*o.y;} };
10
11ld orient(const Pt& a, const Pt& b, const Pt& c){
12    return (b-a).cross(c-a); // >0: CCW, <0: CW, ~0: collinear
13}
14
15bool onSegment(const Pt& a, const Pt& b, const Pt& p){
16    // Check collinearity and bounding box (with EPS)
17    if (sgn(orient(a,b,p)) != 0) return false;
18    ld minx = min(a.x,b.x) - EPS, maxx = max(a.x,b.x) + EPS;
19    ld miny = min(a.y,b.y) - EPS, maxy = max(a.y,b.y) + EPS;
20    return (p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy);
21}
22
23bool segmentsIntersect(const Pt& p1, const Pt& p2, const Pt& q1, const Pt& q2){
24    ld o1 = orient(p1,p2,q1);
25    ld o2 = orient(p1,p2,q2);
26    ld o3 = orient(q1,q2,p1);
27    ld o4 = orient(q1,q2,p2);
28
29    int s1=sgn(o1), s2=sgn(o2), s3=sgn(o3), s4=sgn(o4);
30
31    // Proper intersection if orientations differ strictly
32    if (s1*s2 < 0 && s3*s4 < 0) return true;
33
34    // Handle collinear cases (touching endpoints or overlap)
35    if (s1==0 && onSegment(p1,p2,q1)) return true;
36    if (s2==0 && onSegment(p1,p2,q2)) return true;
37    if (s3==0 && onSegment(q1,q2,p1)) return true;
38    if (s4==0 && onSegment(q1,q2,p2)) return true;
39
40    return false;
41}
42
43int main(){
44    ios::sync_with_stdio(false);
45    cin.tie(nullptr);
46
47    Pt p1(0,0), p2(2,0);
48    Pt q1(1,-1), q2(1,1);
49    Pt r1(3,0), r2(5,0);
50
51    cout << boolalpha;
52    cout << "[p1-p2] with [q1-q2] intersect? " << segmentsIntersect(p1,p2,q1,q2) << "\n"; // true (cross)
53    cout << "[p1-p2] with [r1-r2] intersect? " << segmentsIntersect(p1,p2,r1,r2) << "\n"; // false (disjoint)
54
55    // Collinear overlap example
56    Pt s1(0,0), s2(4,0), t1(2,0), t2(6,0);
57    cout << "[s1-s2] with [t1-t2] intersect? " << segmentsIntersect(s1,s2,t1,t2) << "\n"; // true (overlap)
58
59    return 0;
60}
61

This code implements orientation and a robust closed-segment intersection test. It first checks proper intersection via opposite orientation signs. Then it handles all collinear edge cases with an EPS-extended bounding-box test. This approach works reliably for typical CF inputs with floating coordinates and also tolerates tiny numeric errors.

Time: O(1) per intersection checkSpace: O(1)
Projection, closest point, and distances to line/segment using dot and cross
1#include <bits/stdc++.h>
2using namespace std;
3
4using ld = long double;
5const ld EPS = 1e-12L;
6
7struct Pt{ ld x,y; Pt(){} Pt(ld X, ld Y):x(X),y(Y){} Pt operator+(const Pt&o)const{return {x+o.x,y+o.y};} Pt operator-(const Pt&o)const{return {x-o.x,y-o.y};} Pt operator*(ld k)const{return {x*k,y*k};} ld dot(const Pt&o)const{return x*o.x + y*o.y;} ld cross(const Pt&o)const{return x*o.y - y*o.x;} };
8
9Pt projectPointLine(const Pt& a, const Pt& b, const Pt& p){
10    Pt d = b - a;
11    ld denom = d.dot(d);
12    if (denom < EPS) return a; // a==b: treat as a point
13    ld t = (p - a).dot(d) / denom; // unbounded parameter
14    return a + d * t;
15}
16
17Pt closestPointSegment(const Pt& a, const Pt& b, const Pt& p){
18    Pt d = b - a;
19    ld denom = d.dot(d);
20    if (denom < EPS) return a; // segment is a point
21    ld t = (p - a).dot(d) / denom;
22    t = max((ld)0, min((ld)1, t)); // clamp to segment
23    return a + d * t;
24}
25
26ld distPointLine(const Pt& a, const Pt& b, const Pt& p){
27    Pt d = b - a;
28    if (fabsl(d.x) < EPS && fabsl(d.y) < EPS) return hypotl(p.x - a.x, p.y - a.y);
29    // area = |d x (p-a)|, height = area / |d|
30    return fabsl(d.cross(p - a)) / sqrtl(d.dot(d));
31}
32
33ld distPointSegment(const Pt& a, const Pt& b, const Pt& p){
34    Pt c = closestPointSegment(a,b,p);
35    return hypotl(p.x - c.x, p.y - c.y);
36}
37
38int main(){
39    ios::sync_with_stdio(false);
40    cin.tie(nullptr);
41
42    Pt a(0,0), b(4,0);
43    Pt p(3,2);
44    Pt q(5,3);
45
46    Pt proj = projectPointLine(a,b,p);
47    Pt cp1 = closestPointSegment(a,b,p);
48    Pt cp2 = closestPointSegment(a,b,q);
49
50    cout.setf(ios::fixed); cout << setprecision(10);
51    cout << "Projection of p onto line ab: (" << proj.x << "," << proj.y << ")\n";
52    cout << "Closest point to p on segment ab: (" << cp1.x << "," << cp1.y << ")\n";
53    cout << "Closest point to q on segment ab: (" << cp2.x << "," << cp2.y << ")\n";
54    cout << "dist(p, line ab) = " << distPointLine(a,b,p) << "\n";
55    cout << "dist(p, seg ab) = " << distPointSegment(a,b,p) << "\n";
56    cout << "dist(q, seg ab) = " << distPointSegment(a,b,q) << "\n";
57
58    return 0;
59}
60

Using dot and cross, we compute the projection of a point onto a line, clamp to get the closest point on a segment, and then compute distances. Degenerate segments (a=b) are handled explicitly. Cross over norm yields the perpendicular distance to a line, which is numerically stable and avoids expensive angle computations.

Time: O(1) per querySpace: O(1)
Polygon signed area (shoelace) and orientation using cross products
1#include <bits/stdc++.h>
2using namespace std;
3
4using ll = long long;   // exact integer area*2 if using integer coords
5using ld = long double; // for floating output when desired
6
7struct IPoint { ll x, y; };
8
9// Returns twice the signed area using 64-bit exact arithmetic
10long long signedArea2(const vector<IPoint>& p){
11    int n = (int)p.size();
12    __int128 s = 0; // widen to avoid overflow if inputs are up to ~1e9
13    for(int i=0;i<n;i++){
14        int j = (i+1)%n;
15        s += (__int128)p[i].x * p[j].y - (__int128)p[i].y * p[j].x;
16    }
17    long long r = (long long)s; // assumes final value fits in 64-bit; adjust if necessary
18    return r; // may be negative if CW order
19}
20
21int polygonOrientation(const vector<IPoint>& p){
22    long long a2 = signedArea2(p);
23    if (a2 == 0) return 0; // collinear or degenerate polygon
24    return a2 > 0 ? +1 : -1; // +1: CCW, -1: CW
25}
26
27int main(){
28    ios::sync_with_stdio(false);
29    cin.tie(nullptr);
30
31    vector<IPoint> poly = { {0,0}, {4,0}, {4,3}, {0,3} }; // rectangle
32    long long a2 = signedArea2(poly);
33
34    cout << "signed area * 2 = " << a2 << "\n";
35    cout << "unsigned area = " << fixed << setprecision(1) << ( (long double) llabs(a2) / 2.0L ) << "\n";
36
37    int ori = polygonOrientation(poly);
38    cout << "orientation = " << (ori>0?"CCW": (ori<0?"CW":"degenerate")) << "\n";
39
40    return 0;
41}
42

For integer coordinates, the shoelace sum can be accumulated exactly in 64-bit (optionally widening to 128-bit during accumulation to prevent overflow). signedArea2 returns twice the signed area, which is an integer. The sign indicates polygon orientation (CCW positive). This is robust and avoids floating error entirely for grid-aligned inputs.

Time: O(n) for n verticesSpace: O(1) extra space beyond input