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,RIGHTorSTRAIGHT(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 ofcross(B − A, C − B)(the same sign ascross(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
YESif it is strictly convex (no dent and no straight corner), elseNO.
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
- What does the sign of the cross product mean? Positive: the second vector is counterclockwise (left) of the first; negative: clockwise (right); zero: collinear.
- Why not use angles? Floating point rounds; two different directions can give the same double. The cross product is exact with integers.
- What is the cross product geometrically? The signed area of the parallelogram spanned by the two vectors (twice the triangle's area).
- How big can it get? For |coordinates| ≤ C, up to 8C²:
long longup to C = 10^9,__int128beyond. - What does the dot product tell you? Whether the angle between two vectors is acute (> 0), obtuse (< 0) or right (= 0).
- How do you test convexity? All n turns (with wrap-around) have the same nonzero sign, for a simple polygon.
- 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 longfor 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