Coordinate Geometry
Pillar: FIX — "Fix coordinates, then distances and areas become algebra."
The Power of Coordinates
Coordinate geometry (analytic geometry) is the bridge between geometry and algebra. By placing figures on a coordinate plane, you convert every geometric question — distance, angle, area, collinearity — into an algebraic computation.
In competitive programming, nearly all computational geometry problems work in coordinates. Points are pairs \((x, y)\), and algorithms manipulate them with formulas from this lesson.
The Cartesian Plane
The Cartesian plane has two perpendicular axes:
- The \(x\)-axis (horizontal)
- The \(y\)-axis (vertical)
Every point is identified by an ordered pair \((x, y)\). The origin is \((0, 0)\).
Quadrants
| Quadrant | \(x\) | \(y\) | Example |
|---|---|---|---|
| I | \(+\) | \(+\) | \((3, 4)\) |
| II | \(-\) | \(+\) | \((-2, 5)\) |
| III | \(-\) | \(-\) | \((-1, -3)\) |
| IV | \(+\) | \(-\) | \((4, -2)\) |
Distance Formula
The distance between points \(P_1 = (x_1, y_1)\) and \(P_2 = (x_2, y_2)\) is:
This is just the Pythagorean theorem applied to the right triangle formed by the horizontal and vertical differences.
Example
Distance from \((1, 2)\) to \((4, 6)\):
Squared Distance
In many CP problems, you can avoid the square root entirely by working with squared distance:
This is faster to compute and avoids floating-point errors. You can compare distances using their squares since \(d_1 < d_2 \iff d_1^2 < d_2^2\) for non-negative distances.
Midpoint Formula
The midpoint of \(P_1 = (x_1, y_1)\) and \(P_2 = (x_2, y_2)\) is:
This is just the average of the coordinates.
Example
Midpoint of \((2, 3)\) and \((8, 7)\):
Slope
The slope of the line through \((x_1, y_1)\) and \((x_2, y_2)\) is:
Slope measures the rate of vertical change per unit of horizontal change.
| Slope | Line Direction |
|---|---|
| \(m > 0\) | Rising left to right |
| \(m < 0\) | Falling left to right |
| \(m = 0\) | Horizontal |
| Undefined | Vertical (\(x_1 = x_2\)) |
Parallel and Perpendicular Lines
- Parallel lines have equal slopes: \(m_1 = m_2\)
- Perpendicular lines have slopes that multiply to \(-1\): \(m_1 \cdot m_2 = -1\)
Example. A line has slope \(3\). A perpendicular line has slope \(-\frac{1}{3}\).
Equations of Lines
Slope-Intercept Form
where \(m\) is the slope and \(b\) is the \(y\)-intercept (where the line crosses the \(y\)-axis).
Point-Slope Form
Given a point \((x_1, y_1)\) and slope \(m\):
Standard Form
This form is useful when you need to handle vertical lines (which can't be written in slope-intercept form) and for the point-to-line distance formula.
Converting Between Forms
Example. Write the equation of the line through \((2, 5)\) with slope \(-3\).
Point-slope: \(y - 5 = -3(x - 2)\)
Slope-intercept: \(y = -3x + 6 + 5 = -3x + 11\)
Standard: \(3x + y - 11 = 0\)
Finding Intersections
To find where two lines meet, solve their equations simultaneously.
Example. Find the intersection of \(y = 2x + 1\) and \(y = -x + 7\).
Set equal: \(2x + 1 = -x + 7 \Rightarrow 3x = 6 \Rightarrow x = 2\).
Then \(y = 2(2) + 1 = 5\). The intersection is \((2, 5)\).
Parallel Lines Don't Intersect
If two lines have the same slope but different intercepts, they are parallel and have no intersection point.
Distance from a Point to a Line
The distance from point \((x_0, y_0)\) to the line \(ax + by + c = 0\) is:
Example
Distance from \((3, 1)\) to the line \(4x - 3y + 2 = 0\):
Why This Formula Matters
In CP, this formula lets you quickly determine: - How far a point is from a boundary - Whether a point is "close enough" to a line - The height of a triangle (distance from a vertex to the opposite side)
The Shoelace Formula
The Shoelace formula (also called the Surveyor's formula) computes the area of a polygon given its vertices in order.
For a polygon with vertices \((x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)\) listed in order (clockwise or counterclockwise):
where indices wrap around: \((x_{n+1}, y_{n+1}) = (x_1, y_1)\).
Why "Shoelace"?
Write the coordinates in two columns and cross-multiply diagonally:
| \(x\) | \(y\) |
|---|---|
| \(x_1\) | \(y_1\) |
| \(x_2\) | \(y_2\) |
| \(x_3\) | \(y_3\) |
| \(x_1\) | \(y_1\) |
Multiply along the down-right (\(\searrow\)) diagonals: \(x_1 y_2 + x_2 y_3 + x_3 y_1\).
Multiply along the down-left (\(\swarrow\)) diagonals: \(x_2 y_1 + x_3 y_2 + x_1 y_3\).
Worked Example
Triangle with vertices \(A(1, 2)\), \(B(4, 6)\), \(C(7, 2)\).
Signed Area
Without the absolute value, the Shoelace formula gives a signed area: positive if the vertices are counterclockwise, negative if clockwise. This is useful in CP for:
- Determining orientation (CCW vs CW)
- Checking if a point is inside a polygon
- Computing cross products
Collinearity
Three points \(A\), \(B\), \(C\) are collinear (lie on the same line) if and only if the triangle \(ABC\) has zero area:
Equivalently, the slope from \(A\) to \(B\) equals the slope from \(A\) to \(C\).
Practice Problems
Problem 1. Find the distance between \((-3, 4)\) and \((5, -2)\).
Solution
\(d = \sqrt{(5-(-3))^2 + (-2-4)^2} = \sqrt{64 + 36} = \sqrt{100} = 10\).
Problem 2. A line passes through \((1, 3)\) and \((5, 11)\). Find its equation in slope-intercept form.
Solution
Slope: \(m = \frac{11-3}{5-1} = \frac{8}{4} = 2\).
Point-slope: \(y - 3 = 2(x - 1)\), so \(y = 2x + 1\).
Problem 3. Find the area of the quadrilateral with vertices \((0,0)\), \((4,0)\), \((5,3)\), \((1,4)\).
Solution
Shoelace formula:
\(\searrow\): \(0 \cdot 0 + 4 \cdot 3 + 5 \cdot 4 + 1 \cdot 0 = 0 + 12 + 20 + 0 = 32\)
\(\swarrow\): \(4 \cdot 0 + 5 \cdot 0 + 1 \cdot 3 + 0 \cdot 4 = 0 + 0 + 3 + 0 = 3\)
Area \(= \frac{1}{2}|32 - 3| = \frac{29}{2} = 14.5\).
Problem 4. Find the distance from \((1, 1)\) to the line \(3x + 4y - 15 = 0\).
Solution
\(d = \frac{|3(1) + 4(1) - 15|}{\sqrt{9 + 16}} = \frac{|3 + 4 - 15|}{5} = \frac{8}{5} = 1.6\).
Problem 5. Are the points \((1, 1)\), \((3, 5)\), \((5, 9)\) collinear?
Solution
Check: \(1(5-9) + 3(9-1) + 5(1-5) = -4 + 24 - 20 = 0\).
Yes, they are collinear.
Problem 6. Find the equation of the line perpendicular to \(y = \frac{2}{3}x + 4\) that passes through \((6, 1)\).
Solution
The given line has slope \(\frac{2}{3}\), so the perpendicular slope is \(-\frac{3}{2}\).
Point-slope: \(y - 1 = -\frac{3}{2}(x - 6)\), so \(y = -\frac{3}{2}x + 10\).