Almost every computational-geometry primitive is the cross product in the plane:
(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
- > 0 — c is to the left of the directed line a→b (CCW)
- < 0 — right (CW)
- = 0 — collinear
CSES Point Location Test is this sign. Segment intersection is four orientations (each endpoint vs the other segment) plus a collinear overlap check. Convex hull (Andrew / monotone chain): sort points, scan, pop while the turn is not left.
Integer coordinates. Do not use atan2 for hulls if a cross product will do — floats WA on ties.
function cross(ax, ay, bx, by, cx, cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
function orientation(ax, ay, bx, by, cx, cy) {
const v = cross(ax, ay, bx, by, cx, cy);
if (v > 0) return 1;
if (v < 0) return -1;
return 0;
}Checks 0/2