Geometry basics
Basic contest geometry answers questions about two or three points with integer coordinates, such as which way three points turn or what kind of angle they make, by the sign of a cross product or a dot product of vectors. The sign of an integer is exact, unlike slopes or angles in floating point.
Explanation
Someone walks from A(1, 1) to B(4, 2), then to C(6, 5). At B, do they turn left or right?
Write each step as "how far right, how far up". From A to B the walker goes 3 right and 1 up, and from B to C, 2 right and 3 up. This pair of numbers is the vector of the step. A step that goes down, or towards smaller x, has a negative number.
Fig. 1. Each step is a vector: how far right and how far up.
The cross product
The school way to compare directions is the slope, rise divided by run. The first step has a slope of 1/3 and the second a steeper 3/2, so the walker turns left.
Fig. 2. A walk with five points. The red steps meet at point 4.
Now take a longer walk. The step from point 2 to point 3 goes straight up, so its slope is 3 / 0, a division by zero. At point 4, the step from 3 to 4 is 4 right and 1 down, a slope of −1/4, and the step from 4 to 5 is 2 left and 2 down, a slope of (−2) / (−2) = 1. The slope grew, so the rule says "left", but the figure shows a right turn at point 4. The two minus signs cancelled, and the slope lost the fact that the walker now moves towards smaller x.
The rule "the second slope is bigger" is \frac{dy_2}{dx_2} > \frac{dy_1}{dx_1}, for the steps (dx_1, dy_1) and (dx_2, dy_2). When both steps go rightwards, dx_1 and dx_2 are positive, and multiplying by dx_1 \cdot dx_2 keeps the comparison and removes the division:
This was derived for rightward steps only, so try it on the walk's three turns. At point 2 the steps are (3, 1) and (0, 3): 3·3 − 1·0 = 9, positive, a left turn. At point 3, (0, 3) and (4, −1) give 0·(−1) − 3·4 = −12, a right turn. At point 4, (4, −1) and (−2, −2) give 4·(−2) − (−1)·(−2) = −10, a right turn, as the figure shows.
This number is the cross product of the two vectors, u_x v_y - u_y v_x. Turning the whole picture doesn't change it: a quarter turn to the left takes (3, 1) and (2, 3) to (−1, 3) and (−3, 2), and both pairs give 7. So turn the picture until the first step points right, as (a, 0) with a > 0. The cross product is then a · dy_2, positive when the second step goes up, to the left of the first. A positive cross product means a left turn (counterclockwise), a negative one a right turn, and zero means the three points lie on one line. On one line the walker may go straight on or turn back, as from (0, 0) to (2, 0) to (1, 0).
Fig. 3. The cross product of the blue arrow and the step from B to C changes sign only when C crosses the grey line.
The dot product
The angle at a point is a different question. For the angle at point 4, take both vectors from point 4: (−4, 1) to point 3 and (−2, −2) to point 5. Their dot product u_x v_x + u_y v_y is 8 − 2 = 6, positive, so the angle is less than 90° (acute). A zero dot product means a right angle, and a negative one an angle over 90° (obtuse). With the first vector turned to (a, 0), the dot product is a · dx_2, positive when the second vector leans the same way as the first.
Fig. 4. The dot product of the black vector with each of the others.
The walker's steps (4, −1) and (−2, −2) give −6 instead. The first step points into point 4, not out of it, and reversing a vector flips the sign. The steps' dot product measures the turn: −6 means the walker turns by more than 90°. It also tells apart the two cases of a zero cross product: straight on gives a positive dot product, and turning back a negative one, as (2, 0) and (−1, 0) give −2.
Fig. 5. At point 4 the walker turns by more than 90°, so the angle at point 4 is less than 90°.
Distances
By Pythagoras, a step has length \sqrt{dx^2 + dy^2}: the step from point 1 to point 2 has length \sqrt{10}. To find the closer of two points, compare the squared distances dx^2 + dy^2, which come in the same order and are exact integers. With sqrt in floating point, the distances from O(0, 0) to A(1 000 000 000, 0) and B(999 999 995, 100 000) come out equal, though their squares are 10^{18} and 10^{18} + 25.
Implementation
A point, and a vector too, is a struct with two long long fields: two numbers under one name, like a pair whose fields are called x and y. Each product is a one-line function that takes time:
struct Point { long long x, y; };
Point vec(Point a, Point b) { return {b.x - a.x, b.y - a.y}; } // vector from a to b
long long cross(Point u, Point v) { return u.x * v.y - u.y * v.x; }
long long dot(Point u, Point v) { return u.x * v.x + u.y * v.y; }
long long dist2(Point a, Point b) { Point d = vec(a, b); return dot(d, d); }
// 1: a -> b -> c turns left, -1: turns right, 0: a, b, c on one line
int orient(Point a, Point b, Point c) {
Point u = vec(a, b), v = vec(a, c); // make the vectors from a
long long s = cross(u, v); // multiply
if (s > 0) return 1; // read the sign
if (s < 0) return -1;
return 0;
}return {b.x - a.x, b.y - a.y}; builds a new Point from its two fields. orient takes both vectors from a, yet gets the same sign as the two steps. The vector from a to c is the first step u plus the second step w, and the cross product splits over a sum, so cross(u, u + w) = cross(u, u) + cross(u, w) = cross(u, w): a vector's cross product with itself is zero.
To print which way a, b, c turn, which is also the side of the line ab that c is on:
int o = orient(a, b, c);
if (o > 0) cout << "LEFT\n";
else if (o < 0) cout << "RIGHT\n";
else cout << "ONE LINE\n";To find which of a and b is closer to p (take the root only to print):
if (dist2(p, a) < dist2(p, b)) cout << "A\n";
else if (dist2(p, a) > dist2(p, b)) cout << "B\n";
else cout << "TIE\n";
cout << fixed << setprecision(6) << sqrt((double)dist2(p, a)) << '\n'; // <cmath>, <iomanip>Common mistakes
Swapping the arguments. For A(1, 1), B(4, 2), C(6, 5),
cross(vec(a, b), vec(a, c))is 7 (left) butcross(vec(a, c), vec(a, b))is −7. Use one order everywhere.Forgetting that grid rows grow downwards. The cells (row, column) (0, 0), (0, 1), (1, 1) taken as (x, y) = (column, row) give cross 1, a left turn, but on screen the path goes right, then down: a right turn. Flip the sign of the row.
Similar techniques
Floating-point numbers are for answers that are angles (
atan2of the cross and dot products) or fractions.Lines and segments test a point on a segment and find the distance from a point to a line.
Segment intersection uses four
orienttests.Polygon area adds cross products around the polygon; for a triangle, the absolute cross product is twice its area.
A convex hull keeps only left turns, tested with
orient.
Practice
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry · For Beginners
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry
Very easy · Geometry