SyntaxPilot
Courses/Competitive Programming/Lesson 79
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 79 of 90

Geometry 1: points, vectors, cross product, orientation

queued

These are the notes for Competitive Programming episode 79, the first geometry episode. Contest geometry is about exact arithmetic: with integer coordinates, the cross product tells a left turn from a right turn (or a straight line) using only + − ×, so the answer is never rounded. The Rider's Turn shows the obvious fix, comparing atan2 angles, giving a real Wrong Answer (STRAIGHT on a real right turn with coordinates near 10^9), then a cross product in int that overflows and flips both answers, and the exact long long version. The dot product says ahead or behind. Convex Route (is a polygon convex?) checks that all n turns go the same way; forgetting the two wrap-around turns says YES for a dented field. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

On a scooter, where you are is a place on the map: a point (x, y). How you moved (2 km east, 1 km north) is a movement: a vector, B − A. Whether you turn the steering wheel left or right depends only on two arrows, the way you were going and the way you go next, not on where you are: the cross product turns those two arrows into one number whose sign is the answer. Whether a shop is ahead of you or behind you is another question about two arrows: the dot product.

Problem G1 · The Rider's Turn

(Written for this course.)

  • q ≤ 10^5 queries; each gives integer points A, B, C with |x|, |y| ≤ 10^9.
  • A rider goes A → B → C. Print LEFT, RIGHT or STRAIGHT (A, B, C on one line) for the turn at B. The answer must be exact.
3
0 0 2 0 3 1
0 0 2 0 3 -1
0 0 1 1 2 2

Attempt 1: compare atan2 angles (Wrong Answer)

atan2(dy, dx) is the angle of the arrow (dx, dy). Compare the directions of the two legs:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        ll xa, ya, xb, yb, xc, yc;
        cin >> xa >> ya >> xb >> yb >> xc >> yc;
        double a1 = atan2(yb - ya, xb - xa);        // direction of A -> B
        double a2 = atan2(yc - yb, xc - xb);        // direction of B -> C
        double d = a2 - a1;
        if (d > M_PI) d -= 2 * M_PI;
        if (d <= -M_PI) d += 2 * M_PI;
        if (fabs(d) < 1e-12) cout << "STRAIGHT\n";
        else cout << (d > 0 ? "LEFT\n" : "RIGHT\n");
    }
}
LEFT
RIGHT
STRAIGHT

Now add a fourth query with big coordinates: A = (−999999999, −999999999), B = (0, −1), C = (999999998, 999999996). The legs are (999999999, 999999998) and (999999998, 999999997); the exact cross product is −1, a right turn by about 10^−18 radians.

4
0 0 2 0 3 1
0 0 2 0 3 -1
0 0 1 1 2 2
-999999999 -999999999 0 -1 999999998 999999996
LEFT
RIGHT
STRAIGHT
STRAIGHT

The 4th answer is wrong. Both atan2 values are the same double (checked: a1 == a2 is true), so no epsilon can fix it. We need an integer test.

Points and vectors

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // B - A = the arrow from A to B
};

A point and a vector have the same two numbers; the difference is the meaning: a place versus a movement.

The cross product

  • cross(a, b) = a.x · b.y − a.y · b.x
  • It is the signed area of the parallelogram spanned by a and b.
  • > 0: b points to the left of a (counterclockwise) · < 0: to the right · = 0: same line.
  • Sample: legs (2, 0) and (1, 1): 2·1 − 0·1 = 2 > 0 → LEFT.
  • orient(A, B, C) = the sign of cross(B − A, C − B) (the same sign as cross(B − A, C − A): it is the same triangle).
A B C B − A C − B cross turn
(0,0) (2,0) (3,1) (2,0) (1,1) 2 LEFT
(0,0) (2,0) (3,−1) (2,0) (1,−1) −2 RIGHT
(0,0) (1,1) (2,2) (1,1) (1,1) 0 STRAIGHT

The int overflow bug

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        int xa, ya, xb, yb, xc, yc;
        cin >> xa >> ya >> xb >> yb >> xc >> yc;
        int cr = (xb - xa) * (yc - yb) - (yb - ya) * (xc - xb);   // cross of AB and BC
        if (cr == 0) cout << "STRAIGHT\n";
        else cout << (cr > 0 ? "LEFT\n" : "RIGHT\n");
    }
}
2
0 0 100000 0 100001 30000
0 0 100000 0 100001 -30000
RIGHT
LEFT

Both are wrong: the first turn is clearly left. 100000 · 30000 = 3·10^9 does not fit in an int (max 2147483647), so the sign flips. Two differences of 46341 already overflow (46341² > 2^31).

The fix: long long

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        P a, b, c;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
        int o = orient(a, b, c);
        cout << (o > 0 ? "LEFT" : o < 0 ? "RIGHT" : "STRAIGHT") << "\n";
    }
}
LEFT
RIGHT
LEFT
RIGHT
STRAIGHT
RIGHT

Is long long enough? With |x|, |y| ≤ 10^9 each difference is at most 2·10^9, each product at most 4·10^18, and their difference at most 8·10^18 < 9.22·10^18 = LLONG_MAX. Just enough. For coordinates up to 10^18, compute the products in __int128.

The dot product: ahead or behind

  • dot(a, b) = a.x · b.x + a.y · b.y
  • > 0: the angle between them is under 90° · < 0: over 90° · = 0: exactly 90°.
  • A rider at A facing B: shop C is ahead if dot(B − A, C − A) > 0.
  • cross = which side, dot = which way.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        P a, b, c;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
        ll d = dot(b - a, c - a);                   // is C ahead of the rider at A, facing B?
        cout << (d > 0 ? "AHEAD" : d < 0 ? "BEHIND" : "BESIDE") << "\n";
    }
}
3
0 0 1 0 5 2
0 0 1 0 -3 4
0 0 1 0 0 7
AHEAD
BEHIND
BESIDE

Problem G2 · Convex Route

(Written for this course.)

  • n ≤ 10^5 corners of a simple polygon (the fence never crosses itself), in order, |x|, |y| ≤ 10^9.
  • Print YES if it is strictly convex (no dent and no straight corner), else NO.

Observation. Walking around a convex polygon you turn the same way at every corner. A polygon with n corners has n turns, at p[(i + 1) % n] for i = 0 … n − 1: the last two wrap around.

The wrap-around bug

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    bool left = false, right = false, straight = false;
    for (int i = 0; i + 2 < n; i++) {               // the turn at every middle vertex
        int o = orient(p[i], p[i + 1], p[i + 2]);
        left |= o > 0, right |= o < 0, straight |= o == 0;
    }
    cout << (!straight && !(left && right) ? "YES" : "NO") << "\n";
}

The test: a square field with a dent at the first corner (2, 1):

5
2 1
4 0
4 4
0 4
0 0
YES

Wrong: the loop checks only n − 2 turns and never looks at the turns at the first and last corners.

The fix: n turns, indices mod n

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    bool left = false, right = false, straight = false;
    for (int i = 0; i < n; i++) {                   // the turn at every vertex, wrapping round
        int o = orient(p[i], p[(i + 1) % n], p[(i + 2) % n]);
        left |= o > 0, right |= o < 0, straight |= o == 0;
    }
    cout << (!straight && !(left && right) ? "YES" : "NO") << "\n";
}
NO

A square, counterclockwise:

YES

The same square clockwise (every turn is right, which is fine):

YES

A square with an extra corner in the middle of a side (a straight corner):

5
0 0
2 0
4 0
4 4
0 4
NO

Complexity vs the constraints

Method Time Exact? Verdict
atan2 angles (double) O(1) per query no Wrong Answer on near-straight turns
cross product in int O(1) overflows past ~46341 Wrong Answer
cross product in long long O(1) yes, for |x|, |y| ≤ 10^9 accepted
cross product in __int128 O(1) yes, for |x|, |y| ≤ 10^18 accepted
G2: one orient per corner O(n) yes accepted

Common mistakes (and the real outputs)

Mistake What you see Why Fix
comparing atan2 angles STRAIGHT on a real right turn the two doubles are equal sign of the cross product
int in cross RIGHT LEFT instead of LEFT RIGHT 3·10^9 overflows int long long (or __int128)
checking only n − 2 turns YES for a dented field misses the wrap-around (i + 1) % n, (i + 2) % n
reading coordinates into int then subtracting overflow at 10^9 2·10^9 > INT_MAX read into long long
comparing a double cross product with 0 random answers near 0 rounding of 10^18-sized products integers only
treating STRAIGHT as convex when the problem says strict Wrong Answer collinear corner track straight separately

Mini project

Route turn log. Read a delivery route of n points and print, for every middle point, L, R or S, then the total number of left and right turns, and whether the route is a convex loop (when its last point joins its first). Try it on your own walk to the chai stall.

Practice

These are the homework problems from the episode.

1. Is point C on segment AB? On the line (cross = 0) and between the ends: the arrows from C to A and from C to B point opposite ways (dot(A − C, B − C) ≤ 0).

Solution

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

bool onSegment(P a, P b, P c) {                     // is c on the segment from a to b (ends included)?
    return cross(b - a, c - a) == 0 && dot(a - c, b - c) <= 0;   // on the line, and between the ends
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        P a, b, c;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
        cout << (onSegment(a, b, c) ? "ON" : "OFF") << "\n";
    }
}
ON
OFF
OFF
ON

2. Twice the area of a triangle, exactly. |cross(B − A, C − A)| is twice the area, an integer.

Hint

Print llabs(cross(b - a, c - a)); halve it only when printing, as x / 2 and .5 if it is odd.

3. Count the left turns along a route of n points. Sum orient(p[i], p[i + 1], p[i + 2]) > 0 for i = 0 … n − 3 (a route is not closed, so no wrap-around here).

Hint

The same loop as the buggy G2, which is right for an open route.

4. Is point P strictly inside triangle ABC? P is on the same side of all three edges: the three orients are all +1 or all −1.

Solution

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

bool strictlyInside(P a, P b, P c, P p) {          // p strictly inside triangle abc?
    int o1 = orient(a, b, p), o2 = orient(b, c, p), o3 = orient(c, a, p);
    return (o1 > 0 && o2 > 0 && o3 > 0) || (o1 < 0 && o2 < 0 && o3 < 0);   // same side of all three edges
}

int main() {
    int q;
    cin >> q;
    while (q--) {
        P a, b, c, p;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> p.x >> p.y;
        cout << (strictlyInside(a, b, c, p) ? "INSIDE" : "NOT INSIDE") << "\n";
    }
}
INSIDE
NOT INSIDE
NOT INSIDE
INSIDE

(3, 3) lies on the edge x + y = 6, so it is not strictly inside.

Quick quiz

// A = (1, 1), B = (4, 2), C = (2, 5)
// cross(B − A, C − B) = ?

A) LEFT (cross = 11) · B) RIGHT (cross = −11) · C) STRAIGHT (cross = 0) · D) LEFT (cross = 7)

Answer

A. B − A = (3, 1), C − B = (−2, 3). 3·3 − 1·(−2) = 9 + 2 = 11 > 0: LEFT.

Interview questions

  1. What does the sign of the cross product mean? Positive: the second vector is counterclockwise (left) of the first; negative: clockwise (right); zero: collinear.
  2. Why not use angles? Floating point rounds; two different directions can give the same double. The cross product is exact with integers.
  3. What is the cross product geometrically? The signed area of the parallelogram spanned by the two vectors (twice the triangle's area).
  4. How big can it get? For |coordinates| ≤ C, up to 8C²: long long up to C = 10^9, __int128 beyond.
  5. What does the dot product tell you? Whether the angle between two vectors is acute (> 0), obtuse (< 0) or right (= 0).
  6. How do you test convexity? All n turns (with wrap-around) have the same nonzero sign, for a simple polygon.
  7. How do you test a point on a segment? Cross product zero and dot product of (A − C, B − C) ≤ 0.

Glossary

Term Meaning Example
Point A place (x, y) (2, 0)
Vector A movement; the difference of two points B − A = (2, 0)
struct P A point/vector type with operators P operator-
atan2(dy, dx) The angle of a vector, in radians (double) atan2(1, 1) = π/4
Floating-point rounding Doubles keep ~16 digits two angles become equal
Cross product a.x·b.y − a.y·b.x, signed area cross((2,0),(1,1)) = 2
Orientation (orient) Sign of the cross: +1 / −1 / 0 LEFT / RIGHT / STRAIGHT
Counterclockwise (CCW) Turning left positive cross
Collinear On one straight line (0,0) (1,1) (2,2)
Dot product a.x·b.x + a.y·b.y ahead or behind
Integer overflow A result too big for its type RIGHT LEFT
long long 64-bit integer, up to ~9.2·10^18 exact cross for 10^9
__int128 128-bit integer (GCC) coordinates up to 10^18
Simple polygon A polygon whose sides never cross a farm fence
Convex polygon Every turn the same way, no dent a square
Wrap-around Indices mod n for a closed shape (i + 1) % n
Convex hull The tightest fence around points (next episode) —

Summary

  • Points are places, vectors are movements (B − A).
  • cross(a, b) = a.x·b.y − a.y·b.x: sign = left / right / straight, exact with integers; long long for coordinates up to 10^9.
  • dot(a, b) = a.x·b.x + a.y·b.y: ahead / behind / at a right angle.
  • Never compare angles in doubles; convex ⇔ all n turns (wrapping round) have the same sign.

Solutions in C++, Java and Python

Problem G1 · The Rider's Turn

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        P a, b, c;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
        int o = orient(a, b, c);
        cout << (o > 0 ? "LEFT" : o < 0 ? "RIGHT" : "STRAIGHT") << "\n";
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static long cross(long ax, long ay, long bx, long by) { return ax * by - ay * bx; }   // long: exact up to 10^9
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine().trim());
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long xa = Long.parseLong(st.nextToken()), ya = Long.parseLong(st.nextToken());
            long xb = Long.parseLong(st.nextToken()), yb = Long.parseLong(st.nextToken());
            long xc = Long.parseLong(st.nextToken()), yc = Long.parseLong(st.nextToken());
            long v = cross(xb - xa, yb - ya, xc - xb, yc - yb);
            out.append(v > 0 ? "LEFT" : v < 0 ? "RIGHT" : "STRAIGHT").append('\n');
        }
        System.out.print(out);
    }
}
LEFT
RIGHT
STRAIGHT
RIGHT

Python

import sys

def cross(ax, ay, bx, by):
    return ax * by - ay * bx            # Python ints are exact at any size

data = sys.stdin.read().split()
q = int(data[0])
out = []
for i in range(q):
    xa, ya, xb, yb, xc, yc = map(int, data[1 + 6 * i: 7 + 6 * i])
    v = cross(xb - xa, yb - ya, xc - xb, yc - yb)
    out.append("LEFT" if v > 0 else "RIGHT" if v < 0 else "STRAIGHT")
print("\n".join(out))
LEFT
RIGHT
STRAIGHT
RIGHT

Problem G2 · Convex Route

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
    ll x, y;
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }   // the arrow from o to this
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }   // > 0: b is to the LEFT of a
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }     // > 0: they point the same way
int orient(P a, P b, P c) {                            // +1 left, -1 right, 0 straight
    ll v = cross(b - a, c - b);
    return (v > 0) - (v < 0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for (auto& v : p) cin >> v.x >> v.y;
    bool left = false, right = false, straight = false;
    for (int i = 0; i < n; i++) {                   // the turn at every vertex, wrapping round
        int o = orient(p[i], p[(i + 1) % n], p[(i + 2) % n]);
        left |= o > 0, right |= o < 0, straight |= o == 0;
    }
    cout << (!straight && !(left && right) ? "YES" : "NO") << "\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        long[] x = new long[n], y = new long[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            x[i] = Long.parseLong(st.nextToken()); y[i] = Long.parseLong(st.nextToken());
        }
        boolean left = false, right = false, straight = false;
        for (int i = 0; i < n; i++) {                    // the turn at every corner, wrapping round
            int a = i, b = (i + 1) % n, c = (i + 2) % n;
            long v = (x[b] - x[a]) * (y[c] - y[b]) - (y[b] - y[a]) * (x[c] - x[b]);
            if (v > 0) left = true; else if (v < 0) right = true; else straight = true;
        }
        System.out.println(!straight && !(left && right) ? "YES" : "NO");
    }
}
NO

Python

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
p = [(data[1 + 2 * i], data[2 + 2 * i]) for i in range(n)]
signs = set()
for i in range(n):                       # the turn at every corner, wrapping round
    (ax, ay), (bx, by), (cx, cy) = p[i], p[(i + 1) % n], p[(i + 2) % n]
    v = (bx - ax) * (cy - by) - (by - ay) * (cx - bx)
    signs.add((v > 0) - (v < 0))
print("YES" if 0 not in signs and len(signs) == 1 else "NO")
YES