Cross Product

$a\times b=a_x{b}_y-a_y{b}_x=|a||b|\sin \theta .$

The single most important primitive in 2D geometry. Exact in integers, and it answers orientation, area and parallelism at once.

long long cross(const P& a, const P& b) { return a.x * b.y - a.y * b.x; }
long long cross(const P& o, const P& a, const P& b) {     // relative to origin o
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

What the sign means

$\mathrm{cross}(o,a,b)\{\begin{array}{ll}>0& b\text{ is counter-clockwise from }a\text{ around }o\text{ (left turn)}\\ =0& o,a,b\text{ are collinear}\\ <0& \text{clockwise (right turn)}\end{array}$

This is the orientation test, and it is the basis of:

Task	Test
Is $c$ left of the line $ab$?	$\mathrm{cross}(a,b,c)>0$
Are three points collinear?	$\mathrm{cross}=0$
Convex hull turn direction	sign of the cross product
Do segments $ab$ and $cd$ straddle each other?	opposite signs on both sides
Is a polygon CCW?	signed area $>0$
Is a polygon convex?	all cross products have the same sign
Point inside a convex polygon	same sign for every edge

What the magnitude means

$|a\times b|=\text{area of the parallelogram spanned by }a,b.$

So the triangle area is $\frac{1}{2}|\mathrm{cross}(b-a,c-a)|$, and — crucially — twice the area is an integer for integer input. Work with $2A$ throughout and never divide.

Shoelace formula

$2A=\left|{\sum }_i\mathrm{cross}(p_i,p_{i+1})\right|$

for a simple polygon with $p_n=p_0$. The signed version tells you the orientation as a bonus. See Polygon Area.

Distance from a point to a line

$d(p,\overline{ab})=\frac{|\mathrm{cross}(b-a,p-a)|}{|b-a|}.$

For comparisons, keep the numerator squared and the denominator squared separately, and cross-multiply — no square roots, no floating point:

// is p closer to line ab than q is?
__int128 lhs = (__int128)cross(b-a, p-a) * cross(b-a, p-a) * norm2(d-c);
__int128 rhs = (__int128)cross(d-c, q-c) * cross(d-c, q-c) * norm2(b-a);

Overflow

With coordinates up to $10^9$, differences reach $2\cdot 10^9$ and the cross product reaches $8\cdot 10^{18}$ — inside long long ($9.2\cdot 10^{18}$), but only just. Any further multiplication needs __int128.

If coordinates can be $10^{18}$, use __int128 from the start, or translate all points by the first point to shrink the range.

The sgn idiom

Most uses only need the sign, not the value:

int sgn(long long x) { return (x > 0) - (x < 0); }
int orient(P a, P b, P c) { return sgn(cross(a, b, c)); }

Working with $\{-1,0,1\}$ avoids overflow in comparisons and makes the code read as geometry rather than arithmetic.

3D cross product

$a\times b=(a_y{b}_z-a_z{b}_y,a_z{b}_x-a_x{b}_z,a_x{b}_y-a_y{b}_x),$

a vector perpendicular to both, with length equal to the parallelogram area. Uses:

• plane normal from three points: $(b-a)\times (c-a)$;
• triangle area in 3D: half the length of that;
• coplanarity of four points: the scalar triple product $\mathbf{a}\cdot (\mathbf{b}\times \mathbf{c})=0$;
• tetrahedron volume: $\frac{1}{6}$ of the triple product.

See 3D Geometry.

Why cross beats angles

Comparing angles requires atan2, which is slow, imprecise, and has a discontinuity at $\pm \pi$. The cross product answers the same question exactly, in integers, with two multiplications. Reach for cross first, angles only when you genuinely need a numeric angle.

See also: Dot Product · Orientation Test · Polygon Area