Distances Between Objects

Point to point

long long dist2(P a, P b) { return norm2(a - b); }        // exact, use for comparisons
double dist(P a, P b) { return sqrt((double)dist2(a, b)); }

Point to line

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

double distToLine(P p, P a, P b) {
    return fabs((double)cross(b - a, p - a)) / abs_(b - a);
}

Point to segment

Project, clamp, measure:

double distToSegment(P p, P a, P b) {
    if (a == b) return dist(p, a);
    double t = (double)dot(p - a, b - a) / norm2(b - a);
    t = max(0.0, min(1.0, t));
    P proj{a.x + (b.x - a.x) * t, a.y + (b.y - a.y) * t};
    return dist(p, proj);
}

The clamp handles the case where the perpendicular foot falls outside the segment, in which case the nearest point is an endpoint.

Segment to segment

If they intersect, the distance is 0. Otherwise it is achieved at an endpoint:

double segToSeg(P a, P b, P c, P d) {
    if (segmentsIntersect(a, b, c, d)) return 0;
    return min({distToSegment(a, c, d), distToSegment(b, c, d),
                distToSegment(c, a, b), distToSegment(d, a, b)});
}

The intersection check first is essential — otherwise crossing segments report a positive distance.

Point to polygon

• Inside (test first) → distance 0, or the distance to the nearest edge if the problem wants the boundary.
• Outside → the minimum over all edges of distToSegment. $O(n)$.
• Convex polygon, many queries → binary search the angular sector, $O(\log n)$ per query.

Circles

Pair	Distance
Point to circle	$||p-c|-r|$ (0 if on the circle)
Circle to circle (external)	$|c_1-c_2|-r_1-r_2$, or 0 if $\le 0$
Circle inside circle	$r_1-r_2-|c_1-c_2|$ if nested
Line to circle	$\max (0,d(c,\text{line})-r)$
Segment to circle	$\max (0,\mathrm{distToSegment}(c,a,b)-r)$

Convex polygon to convex polygon

$O(n+m)$ with rotating calipers, or via the Minkowski difference: the distance between two convex polygons equals the distance from the origin to $A\ominus B=A\oplus (-B)$, which is itself convex.

Other metrics

Metric	Formula	Note
Euclidean ($L_2$)	$\sqrt{\Delta x^2+\Delta y^2}$	the default
Manhattan ($L_1$)	$|\Delta x|+|\Delta y|$	grid movement
Chebyshev ($L_{\infty }$)	$\max (|\Delta x|,|\Delta y|)$	king moves
Minkowski $L_p$	$(|\Delta x{|}^p+|\Delta y{|}^p{)}^{1/p}$	interpolates

The rotation trick

$L_1\text{ in }(x,y)⟷L_{\infty }\text{ in }(x+y,x-y).$

Rotating by 45° converts Manhattan distance into Chebyshev distance, which decouples the coordinates — so “maximum Manhattan distance among $n$ points” becomes $\max (\max u-\min u,\max v-\min v)$ in $O(n)$. See Manhattan Geometry.

In $d$ dimensions, the same idea gives ${\max }_{\text{sign pattern}}$ over $2^{d-1}$ transformed coordinates.

Nearest-neighbour queries

Situation	Method
One query, $n$ points	linear scan, $O(n)$
Many queries, static points	KD-tree, $O(\log n)$ expected
Closest pair among $n$	divide and conquer, $O(n\log n)$
Nearest among points on a convex hull	rotating calipers
Nearest with insertions	Delaunay / Voronoi, or a rebuilt KD-tree
High dimensions	LSH / approximate

Precision reminder

Compare squared distances wherever possible. Take the square root only for output, and print with enough precision (printf("%.10f") or cout << fixed << setprecision(10)).

See also: Geometry Basics · Manhattan Geometry · Closest Pair