Why this matters when you build with AI
Ask an AI tool for a geometry solution and it often writes the whole thing with double and a tolerance such as 1e-9 for every comparison. That passes the sample and fails on hidden tests with coordinates near 10^9. A double keeps about 16 decimal digits, and the cross product of two such coordinates needs about 19, so small differences vanish. The same tool often writes a normalize function that divides by the length of a zero vector, and an integer cross product that overflows without any warning.
You can catch all three in a few minutes if you know the exact formulas and test a few hand-made cases: a zero vector, collinear points, and coordinates at the edge of the allowed range. This lesson gives those formulas in C++17, shows the real output of each test, and gives the limits in numbers you can check.
Some terms first. A point is a pair of integers (x, y) that names a location. A vector is the arrow from one point to another, and it is stored as the same pair of numbers: the vector from a to b is b - a. Two vectors are parallel when one is a multiple of the other. Points are collinear when they all lie on one straight line.
The idea: two products that carry meaning
Take two vectors a = (ax, ay) and b = (bx, by).
The dot product is ax * bx + ay * by. It is a single integer. Its meaning comes from the angle t between the two arrows: dot = |a| * |b| * cos(t), where |a| is the length of a. So the sign of the dot product tells you the kind of angle:
- Dot is 0: the arrows are perpendicular (or one of them is the zero vector).
- Dot is positive: the angle is less than 90 degrees.
- Dot is negative: the angle is more than 90 degrees.
A second use is projection. The length of b measured along the direction of a is dot / |a|. Take a = (3, 4) and b = (5, 0). The dot product is 15, and |a| = 5, so b projects to length 3 along a. To avoid square roots, you keep the fraction: the projection of b onto a has length 15 / 5. That is the form most contest solutions use.
The cross product is ax * by - ay * bx. It is also one integer. Its meaning is cross = |a| * |b| * sin(t), where t is the signed angle from a to b, counterclockwise positive. So:
- Cross is positive:
bis counterclockwise froma. If you walk alonga,bis a left turn. - Cross is negative:
bis clockwise froma, a right turn. - Cross is 0: the arrows are parallel or one is the zero vector.
The absolute value of the cross product is the area of the parallelogram spanned by a and b. A triangle with corners A, B and C has area |cross(B - A, C - A)| / 2. Keep the factor of 2 out of the code by working with the doubled area, which is an integer. Worked example: A = (0, 0), B = (4, 0), C = (1, 3). Then B - A = (4, 0) and C - A = (1, 3), and 4 * 3 - 0 * 1 = 12. The doubled area is 12, so the triangle has area 6. Check it another way: base 4, height 3, area 4 * 3 / 2 = 6.
Two worked turns
Take a = (1, 0) and b = (0, 5). Walking east along a and then turning to b (north) is a left turn. The cross product is 1 * 5 - 0 * 0 = 5, positive. Swap the order and cross(b, a) = 0 * 0 - 5 * 1 = -5, negative, a right turn. The magnitude is the same, and only the sign flips. The dot product is 0 in both orders, because the arrows are perpendicular. The dot product cannot tell a left turn from a right turn. Only the cross product can.
Why zero and collinear cases need care
Both products are 0 for the zero vector. So a zero vector looks parallel and perpendicular to everything at once, which is a sign that it has no direction. Any code that takes an angle or a direction of a vector must check for zero first.
Collinear points give a cross product of 0, but they can lie on the same side or on opposite sides of a point. The dot product separates the two cases. For a = (3, -2) and b = (-6, 4), the cross product is 0 and the dot product is 3 * (-6) + (-2) * 4 = -26. The dot product is negative, so b points the opposite way from a. The two vectors are on one line, but in opposite directions.
The C++ code: a small vector library
The library below is the whole set of tools for this lesson. It uses long long for every coordinate, and each function is a single line. The main function holds seven hand-made cases with expected values written out by hand before the run.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
};
P operator+(P a, P b) { return {a.x + b.x, a.y + b.y}; }
P operator-(P a, P b) { return {a.x - b.x, a.y - b.y}; }
P operator*(P a, ll k) { return {a.x * k, a.y * k}; }
bool operator==(P a, P b) { return a.x == b.x && a.y == b.y; }
// Dot product: a.x*b.x + a.y*b.y. Zero when the vectors are perpendicular.
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }
// Cross product (2D): a.x*b.y - a.y*b.x.
// Positive when b turns left (counterclockwise) from a, negative for right, zero when parallel or one is zero.
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
// Squared length. Stays an integer, so no square root is needed for comparisons.
ll norm2(P a) { return dot(a, a); }
// Sign of a number: -1, 0 or 1.
int sgn(ll v) { return (v > 0) - (v < 0); }
int main() {
// Hand-made cases: name, a, b, expected dot, expected cross
struct Case { const char *name; P a, b; ll d, c; };
vector<Case> cases = {
{"perpendicular", {1, 0}, {0, 1}, 0, 1},
{"same direction", {2, 3}, {4, 6}, 26, 0},
{"opposite", {1, 2}, {-2, -4}, -10, 0},
{"left turn", {1, 0}, {0, 5}, 0, 5},
{"right turn", {0, 1}, {1, 0}, 0, -1},
{"zero vector", {0, 0}, {7, -3}, 0, 0},
{"collinear, scaled by -2", {3, -2}, {-6, 4}, -26, 0},
};
bool ok = true;
for (auto &t : cases) {
ll d = dot(t.a, t.b), c = cross(t.a, t.b);
bool pass = (d == t.d && c == t.c);
ok = ok && pass;
printf("%-32s dot=%4lld cross=%3lld %s\n", t.name, d, c, pass ? "ok" : "FAIL");
}
printf("sign of cross((1,0),(0,5)) = %d\n", sgn(cross({1, 0}, {0, 5})));
printf("norm2((3,4)) = %lld\n", norm2({3, 4}));
printf("all hand-made cases: %s\n", ok ? "pass" : "fail");
return ok ? 0 : 1;
}Real output, compiled with g++ -std=c++17 -O2 -Wall -Wextra:
perpendicular dot= 0 cross= 1 ok
same direction dot= 26 cross= 0 ok
opposite dot= -10 cross= 0 ok
left turn dot= 0 cross= 5 ok
right turn dot= 0 cross= -1 ok
zero vector dot= 0 cross= 0 ok
collinear, scaled by -2 dot= -26 cross= 0 ok
sign of cross((1,0),(0,5)) = 1
norm2((3,4)) = 25
all hand-made cases: passThe first line of the table shows the rule to remember. Perpendicular vectors have dot 0, but the cross product is 1, so the test for "is this a right angle" is the dot product and the test for "is this a turn" is the cross product.
The same formulas in Python are short enough to run in your browser. This snippet has no input and prints the same cases:
Real output of that snippet:
perpendicular dot= 0 cross= 1
left turn dot= 0 cross= 5
right turn dot= 0 cross= -1
zero vector dot= 0 cross= 0
collinear, scaled by -2 dot=-26 cross= 0
big ints are exact: 999999999999999999999999999999999999999999999999999999999999Python integers have no size limit, so the Python version never overflows. That is why it is a good checker. In C++ the limit matters, and the next section gives it.
Overflow bounds
A signed 64-bit long long holds values up to 2^63 - 1, which is 9223372036854775807 or about 9.2 * 10^18. Any value above that wraps around in unsigned arithmetic, and in signed arithmetic it is undefined behaviour. Undefined behaviour means the C++ standard allows any result, so the compiler may produce a wrong number or assume the case never happens.
Start with raw vectors whose coordinates satisfy |x| <= C and |y| <= C. Each product in the dot or cross product is at most C * C in size. The sum or difference of two products is at most 2 * C * C. For this to fit in a signed 64-bit integer, 2 * C * C <= 2^63 - 1. The largest such C is 2^31 - 1 = 2147483647, because 2 * (2^31)^2 = 2^63 is one too big. You can check this with 2 * (2**31 - 1)**2 <= 2**63 - 1, which is True, and 2 * (2**31)**2 <= 2**63 - 1, which is False.
For points, the useful bound is on the differences. A point with coordinates in [-10^9, 10^9] gives differences at most 2 * 10^9 in size. Then each product is at most 4 * 10^18, and the cross product is at most 8 * 10^18. That is below 9.2 * 10^18, so long long is safe for the standard input range of most contest problems. It is a narrow margin, and the code must compute the cross product from differences, not from the raw points, for the bound to hold.
A boundary case confirms it. The program below uses a = (2 * 10^9, 2 * 10^9) and b = (-2 * 10^9, 2 * 10^9), which gives the largest magnitude that the point bound allows. It then uses coordinates of 4 * 10^9, which is beyond the bound, and prints the exact value with __int128, a 128-bit integer that GCC provides as an extension to C++. The __int128 type is a compiler feature, not part of the standard, so use it only on a judge that accepts GCC.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Print a signed 128-bit integer in decimal.
string to_str(__int128 v) {
if (v == 0) return "0";
bool neg = v < 0;
unsigned __int128 u = neg ? -(unsigned __int128)v : (unsigned __int128)v;
string s;
while (u > 0) { s += char('0' + (int)(u % 10)); u /= 10; }
if (neg) s += '-';
reverse(s.begin(), s.end());
return s;
}
int main() {
// Point differences with coordinates in [-1e9, 1e9]: each difference is at most 2e9.
ll M = 2000000000LL;
// Largest magnitude: a = (M, M) and b = (-M, M), so cross = M*M - M*(-M) = 2*M*M = 8e18.
ll cross_big = M * M - M * (-M);
printf("safe case: cross((2e9,2e9),(-2e9,2e9)) = %lld\n", cross_big);
// Beyond the bound: coordinates up to 4e9.
ll A = 4000000000LL;
ll ax = A, ay = A, bx = A, by = -A;
__int128 exact = (__int128)ax * by - (__int128)ay * bx;
unsigned long long wrapped = (unsigned long long)ax * (unsigned long long)by
- (unsigned long long)ay * (unsigned long long)bx;
printf("beyond case: a=(%lld,%lld) b=(%lld,%lld)\n", ax, ay, bx, by);
printf("exact cross (__int128) = %s\n", to_str(exact).c_str());
printf("unsigned wrap of the same expression = %llu\n", wrapped);
printf("signed long long cross is undefined behaviour, so it is not printed here\n");
return 0;
}Real output, compiled with g++ -std=c++17 -O2 -Wall -Wextra:
safe case: cross((2e9,2e9),(-2e9,2e9)) = 8000000000000000000
beyond case: a=(4000000000,4000000000) b=(4000000000,-4000000000)
exact cross (__int128) = -32000000000000000000
unsigned wrap of the same expression = 4893488147419103232
signed long long cross is undefined behaviour, so it is not printed hereThe exact value is -3.2 * 10^19, which is outside the long long range. The wrapped number 4893488147419103232 is what unsigned arithmetic gives for the same expression. A signed program that computes this product gives no reliable number at all, and nothing in the output warns you. The Python check of the same expression gives the same wrapped value, so the wrap is not a compiler quirk.
The random test below checks the library on 200,000 random pairs of raw vectors with coordinates in [-10^9, 10^9]. The generator computes dot and cross in long long, and a Python script recomputes each one with unbounded integers. The run found 0 mismatches. It checks that the formulas and the bound agree in the range where the bound holds.
Complexity
Each dot product, cross product and squared length is a fixed number of multiplications and additions, so each call takes O(1) time and uses no extra memory. Checking all pairs of n vectors is O(n^2), so the formulas themselves are not the bottleneck in a contest. Later lessons use the cross product inside sorting and hull algorithms, where a single comparison is called O(n log n) times.
Common mistakes
Using a tolerance on an exact integer. A check such as fabs(cross) < 1e-9 treats a cross product of 1 as zero when the number is a double with a rounding error. With integers there is no error to forgive. Keep the values as long long and test cross == 0. Lesson 02 shows the same failure at the level of angles.
Dividing by the length of a zero vector. The normalize function v / |v| needs |v| > 0. A test run with double gives -nan (not a number), and the value then spreads through every later calculation. An integer division by zero is worse: the program stops with a floating point exception. A program that computed 7 / 0 at run time stopped with exit code 136, which is the code for a floating point exception on Linux. Check for the zero vector before any division.
Swapping the operands of the cross product. cross(a, b) and cross(b, a) have opposite signs. A left turn becomes a right turn and the answer flips. The hand-made test with (1, 0) and (0, 5) catches it at once, because the output shows cross=5 where the right-turn case must show -1.
Reading dot = 0 as collinear. Dot 0 means the vectors are perpendicular. The vectors (1, 0) and (0, 5) have dot 0 and cross 5, so they are not collinear at all. Collinear means cross 0.
Forgetting that points are not vectors. Adding two points has no meaning, and the same struct makes it compile. Keep points for locations and subtract to get vectors before you take a dot or cross product of two arrows.
Missing the overflow bound. The symptom is a value far from the true one, such as the wrapped 4893488147419103232 shown above, with no error. Write the bound next to the code, and switch to __int128 when the coordinates go beyond it.
Checklist to keep
- Use
long longfor every coordinate and every dot or cross product, and test== 0on the exact value. - Compute the cross product of point differences,
cross(b - a, c - a), not of raw coordinates. - Check the zero vector before any division or normalization.
- Use the sign of the cross product for left and right turns, and the sign of the dot product for acute and obtuse angles.
- Write the coordinate bound in a comment: for points in
[-10^9, 10^9]the cross of differences fits inlong long. - Compare a fast formula with the Python version on random inputs before you trust it.
Hands-on exercise
Write the vector library above on your own machine, without copying it. Then write your own hand-made cases. Include at least one zero vector, one collinear pair with the same direction, one collinear pair with opposite directions, one left turn and one right turn. Print the dot and cross for each.
Then write a generator that prints 100,000 random pairs with coordinates in [-10^9, 10^9], and a Python checker that recomputes each dot and cross with unbounded integers. Report the number of mismatches. A good answer prints mismatches 0. If you see a mismatch, check the bound first: a coordinate just above the limit is the usual cause.
Keep your random seed fixed, so a failure can be repeated.
Prompt to try with an AI tool
Use this prompt, then check the answer with the steps above:
Write a C++17 struct for 2D points with integer coordinates in [-1e9, 1e9].
Add functions for the dot product and the cross product of two vectors, and
a function that returns the doubled area of the triangle with corners A, B, C.
Use long long, do not use double anywhere, and explain in two sentences why
the cross product of two differences fits in 64 bits. Then give three test
inputs with the expected output for each, including one collinear triple.A good answer uses long long, computes the doubled area as cross(B - A, C - A) with the absolute value taken at the end, and says that the bound is 8 * 10^18. Check the test with a collinear triple: the doubled area must be 0. Reject an answer that uses sqrt, double or a tolerance for the zero test. A common failure is to use cross(A, B) for the area, which is the wrong formula when A is not the origin.
Summary
Points and vectors are pairs of integers. The dot product gives angles and projections, and the cross product gives turn direction and area. Both are exact in long long when the coordinates are below the bound you computed, and above it you need __int128. Check the zero vector and the collinear cases on purpose, because they are where code fails.
Practice
These take a few minutes each. Try them on paper or in your scratch folder before you open the answers.
Practice 1: dot and cross by hand
Find the dot product and the cross product of a = (2, 5) and b = (-5, 2). Say whether b is a left or right turn from a, and whether the two vectors are perpendicular.
Hint: Multiply the x parts and the y parts for the dot product. For the cross product, multiply ax * by and subtract ay * bx.
Show the answer
The dot product is 2 * (-5) + 5 * 2 = -10 + 10 = 0. The cross product is 2 * 2 - 5 * (-5) = 4 + 25 = 29. The dot product is 0, so the vectors are perpendicular. The cross product is positive, so b is a left turn from a.
Practice 2: doubled area of a triangle
The corners of a triangle are A = (0, 0), B = (4, 0) and C = (1, 3). Find the doubled area and the area. Then find the doubled area when C is moved to (2, 3).
Hint: Compute cross(B - A, C - A), and take the absolute value only at the end.
Show the answer
With C = (1, 3) the cross product is 4 * 3 - 0 * 1 = 12, so the doubled area is 12 and the area is 6. With C = (2, 3) the cross product is 4 * 3 - 0 * 2 = 12, and the doubled area is still 12. Moving C along a line parallel to AB does not change the height, which is why the area stays 6.
Practice 3: the overflow bound
Find the largest integer C such that every dot product and cross product of two vectors with |x| <= C and |y| <= C fits in a signed 64-bit integer. Check your answer with Python.
Hint: The sum of two products is at most 2 * C * C. Find the largest C with 2 * C * C <= 2^63 - 1.
Show the answer
The answer is C = 2147483647, which is 2^31 - 1. In Python, 2 * (2**31 - 1)**2 <= 2**63 - 1 is True, and 2 * (2**31)**2 <= 2**63 - 1 is False, so 2^31 is one too big. Note that this bound is for raw vectors. For point differences in [-10^9, 10^9] the bound is much looser, and 8 * 10^18 still fits.
Practice 4: projection of one vector onto another
Find the projection of b = (5, 0) onto a = (3, 4), both as a length and as a point on the line through the origin in the direction of a.
Hint: The length along a is dot / |a|, and |a|^2 = 25 is an integer. The point is (dot / |a|^2) * a.
Show the answer
The dot product is 3 * 5 + 4 * 0 = 15, and |a|^2 = 3 * 3 + 4 * 4 = 25, so |a| = 5. The length of the projection is 15 / 5 = 3. The projected point is (15 / 25) * (3, 4) = (9/5, 12/5). Check: (9/5, 12/5) lies on the line through the origin and (3, 4), and the vector from it to (5, 0) is (16/5, -12/5), which is perpendicular to (3, 4) because 3 * 16/5 + 4 * (-12/5) = 0.