i. Points, Vectors and Orientation

Geometry Basics

Computational geometry punishes sloppiness. The two decisions that determine whether your solution works are made before you write any algorithm: what number type, and what comparison rule.

Rule 1: stay in integers if you possibly can

With integer input coordinates, these are all exact integer computations:

• cross product and orientation,
• squared distances,
• polygon area (twice the area is an integer),
• segment intersection tests,
• convex hull,
• point-in-polygon.

Only when you need an actual intersection point, a length, or an angle must you leave the integers. Delay that as long as possible.

Overflow: with coordinates up to $10^9$, a difference reaches $2\cdot 10^9$ and a cross product reaches $4\cdot 10^9\cdot 2=8\cdot 10^{18}$ — inside long long ($9.22\cdot 10^{18}$) but only just. A squared distance times another squared distance, or a determinant used for the in-circle test, is not. Use __int128 when in doubt.

Rule 2: one epsilon, used consistently

const double EPS = 1e-9;
int sgnd(double x) { return (x > EPS) - (x < -EPS); }
bool eq(double a, double b) { return fabs(a - b) < EPS; }

Never write a == b on floating point. Choose $\epsilon$ relative to the coordinate magnitude: with values around $10^9$ and double’s 15-16 significant digits, absolute precision is about $10^{-7}$ — so $\epsilon =10^{-9}$ is too small and will misclassify. Use $10^{-6}$ there, or switch to long double, or rescale.

Rule 3: compare by squared distance, never by square root

if (norm2(a - p) < norm2(b - p)) /* a is closer to p than b, exact */;

Taking a square root just to compare two distances throws away exactness for nothing — ​ is monotone, so the comparison on squares gives the same answer. Same for “is this distance $\le r$”: compare $d^2\le r^2$. Only take the square root when a length must appear in the output.

Rule 4: prefer cross-product sorting to atan2

$atan2(y,x)$ gives the angle in $(-\pi ,\pi ]$ and handles all four quadrants, but sorting by it is slow (a transcendental call per comparison) and, on nearly-opposite vectors, imprecise. Angular sort by half-plane and cross product instead — exact for integer input and noticeably faster.

Common degeneracies to test

The cases that break geometry code

• Collinear points (a hull with all points on a line)
• Duplicate points
• Zero-length segments
• $n=1$ or $n=2$
• Polygons given clockwise instead of counter-clockwise
• Points exactly on a boundary (in / out / on?)
• Vertical lines (a slope of infinity)
• Segments that touch at an endpoint
• Concave and self-intersecting polygons where the algorithm assumes convex

Write the degenerate cases into your own test file before submitting. In geometry they are the rule, not the exception.

Orientation convention

Use counter-clockwise positive throughout: $\mathrm{cross}(a,b)>0$ means $b$ is counter-clockwise from $a$. Store polygons CCW; if the input might be CW, check the signed area and reverse.

Precision escape hatches

1. Rational arithmetic — store fractions as pair<long long,long long> with reduction. Exact but slow and prone to overflow.
2. long double — 18-19 significant digits on x86, one line to switch, often enough.
3. __int128 — for exact integer products that exceed 64 bits.
4. Rescale the input — if coordinates are huge but the answer only depends on differences, translate to the centroid first.
5. Adaptive exact predicates (Shewchuk) — a fast floating-point estimate with a certified error bound, falling back to exact arithmetic only when the estimate is inconclusive. What production geometry kernels do; rarely needed in contest code because inputs are usually integral.

The point struct

A point and a vector are the same pair of numbers; the difference is interpretation. Treating points as position vectors and differences as direction vectors removes most of the case analysis from geometry code.

struct P {
    ll x, y;
    P operator+(const P& o) const { return {x + o.x, y + o.y}; }
    P operator-(const P& o) const { return {x - o.x, y - o.y}; }
    P operator*(ll k) const { return {x * k, y * k}; }
    bool operator<(const P& o) const { return x != o.x ? x < o.x : y < o.y; }
    bool operator==(const P& o) const { return x == o.x && y == o.y; }
};
 
ll cross(const P& a, const P& b) { return a.x * b.y - a.y * b.x; }
ll cross(const P& o, const P& a, const P& b) { return cross(a - o, b - o); }   // relative to o
ll dot(const P& a, const P& b)   { return a.x * b.x + a.y * b.y; }
ll dot(const P& o, const P& a, const P& b) { return dot(a - o, b - o); }
ll norm2(const P& a) { return dot(a, a); }                 // squared length
double abs_(const P& a) { return sqrt((double)norm2(a)); }
ll dist2(const P& a, const P& b) { return norm2(a - b); }  // exact, use for comparisons
double dist(const P& a, const P& b) { return sqrt((double)dist2(a, b)); }
 
struct PD { double x, y; };                          // the floating-point twin of P
PD operator+(PD a, PD b) { return {a.x + b.x, a.y + b.y}; }
PD operator-(PD a, PD b) { return {a.x - b.x, a.y - b.y}; }
PD operator*(PD a, double k) { return {a.x * k, a.y * k}; }
PD toPD(P a) { return {(double)a.x, (double)a.y}; }
double cross(PD a, PD b) { return a.x * b.y - a.y * b.x; }     // same names, overloaded on PD
double cross(PD o, PD a, PD b) { return cross(a - o, b - o); }
double dot(PD a, PD b)   { return a.x * b.x + a.y * b.y; }
double dot(PD o, PD a, PD b) { return dot(a - o, b - o); }
double norm2(PD a)       { return dot(a, a); }
double abs_(PD a)        { return sqrt(norm2(a)); }

Two operations do almost all the work: cross (orientation, area, parallelism) and dot (angle sign, projection, perpendicularity).

Never scale an integer P by a double

P’s operator* takes a ll; passing a double silently truncates it to an integer before multiplying, which is almost never what you want ($t=0.7$ becomes $0$). Any construction that is inherently fractional — rotation by a general angle, scaling to a target length, a point partway along a segment — must live in PD, not P. The functions below take P input (exact) but return PD.

Standard transformations

P perp(P a) { return {-a.y, a.x}; }                  // rotate 90 degrees CCW, exact, stays in P
PD perp(PD a) { return {-a.y, a.x}; }                // same, for a floating direction
PD rotate(P a, double t) {                           // rotate by angle t
    return {a.x * cos(t) - a.y * sin(t), a.x * sin(t) + a.y * cos(t)};
}
PD scaleTo(P a, double len) { double d = abs_(a); return {a.x * len / d, a.y * len / d}; }
PD reflectAcross(P p, P a, P b) {                    // reflect p across line ab
    P d = b - a;
    double t = (double)dot(p - a, d) / norm2(d);
    PD proj = toPD(a) + toPD(d) * t;
    return proj * 2 - toPD(p);
}

perp is exact in integers and is the most useful of these — perpendicular bisectors, normals, and half-plane directions all come from it.

Complex numbers as points

std::complex<double> gives vector arithmetic for free:

using Pc = complex<double>;
double dotC(Pc a, Pc b)   { return (conj(a) * b).real(); }
double crossC(Pc a, Pc b) { return (conj(a) * b).imag(); }
Pc rotateC(Pc a, double t){ return a * polar(1.0, t); }
// abs(a); arg(a); norm(a);                            // length, angle, squared length

Multiplication by $e^{i\theta }$ is rotation, which makes rotation code trivial, and conj(a)*b packs dot into the real part and cross into the imaginary part in one multiplication. The drawbacks: it forces floating point (losing integer exactness), and norm means squared length in <complex>, which surprises people. Use it for rotation-heavy problems, a plain integer struct P otherwise.

Dot Product

$a\cdot b=a_x{b}_x+a_y{b}_y=|a||b|\cos \theta .$

The dot product measures alignment.

What the sign means

$a\cdot b\{\begin{array}{ll}>0& \text{angle}<90°\text{(same general direction)}\\ =0& \text{perpendicular}\\ <0& \text{angle}>90°\end{array}$

Task	Test
Is the angle at $b$ in triangle $abc$ obtuse?	$\mathrm{dot}(b,a,c)<0$
Is the triangle right-angled?	some $\mathrm{dot}=0$
Is point $p$ within the “slab” of segment $ab$ (perpendicular to $ab$ through $a$, and through $b$)?	$\mathrm{dot}(a,b,p)\ge 0$ and $\mathrm{dot}(b,a,p)\ge 0$
Are two lines perpendicular?	direction $\mathrm{dot}=0$
Is $p$ on ray $ab$ (given collinear)?	$\mathrm{dot}(b-a,p-a)\ge 0$

Proof: $a\cdot b=|a||b|\cos \theta$ and the sign table

By the law of cosines on the triangle with sides $a$, $b$, $a-b$ (as vectors from the origin), the angle $\theta$ between $a$ and $b$ satisfies
$|a-b{|}^2=|a{|}^2+|b{|}^2-2|a||b|\cos \theta .$
Expanding the left side coordinate-wise, $|a-b{|}^2=|a{|}^2-2(a_x{b}_x+a_y{b}_y)+|b{|}^2$. Comparing the two expressions gives $a_x{b}_x+a_y{b}_y=|a||b|\cos \theta$, which is $a\cdot b$. Since $|a|,|b|\ge 0$, the sign of $a\cdot b$ is exactly the sign of $\cos \theta$, which is positive for $\theta \in [0,90°)$, zero at $90°$, negative for $\theta \in (90°,180°]$ — the claimed table. $■$

Projection

${\mathrm{proj}}_b(a)=\frac{a\cdot b}{|b{|}^2}b,\text{scalar projection}=\frac{a\cdot b}{|b|}.$

// closest point on the LINE through a,b to point p
double t = (double)dot(p - a, b - a) / norm2(b - a);
PD closest = toPD(a) + toPD(b - a) * t;
 
// closest point on the SEGMENT: clamp t to [0,1] first

The clamp is the whole difference between “closest point on the line” and “closest point on the segment” — a one-line change that is easy to forget.

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));
    double px = a.x + (b.x - a.x) * t, py = a.y + (b.y - a.y) * t;
    return hypot(p.x - px, p.y - py);
}

Squared distance — use it, not the root

Exact in integers, no square root, and order-preserving (Rule 3). Use it for comparing distances, “is this within radius $r$” ($d^2\le r^2$), nearest-neighbour searches, and closest pair.

Law of cosines and the angle between vectors

$|c{|}^2=|a{|}^2+|b{|}^2-2(a\cdot b)$
is exactly the identity proved above, rearranged. For the magnitude of the angle itself:

double angle(P a, P b) {            // angle between vectors, in [0, pi]
    return atan2(fabs((double)cross(a, b)), (double)dot(a, b));
}

Proof: atan2(|cross|, dot) is more stable than acos(dot/(|a||b|))

Both compute $\theta =\angle (a,b)\in [0,\pi ]$, since $(\mathrm{cross}(a,b),\mathrm{dot}(a,b))=|a||b|(\sin \theta ,\cos \theta )$ up to the positive scale $|a||b|$, and atan2 is scale-invariant in its two arguments ($atan2(ky,kx)=atan2(y,x)$ for $k>0$).

The acos route first divides by $|a||b|$ — a source of rounding error — and then applies $\arccos$, whose derivative $-1/\sqrt{1-u^2}$ diverges as $u\to \pm 1$, i.e. exactly where $\theta \to 0$ or $\theta \to \pi$. A tiny input error near $u=\pm 1$ (including, from floating-point rounding, $u$ landing outside $[-1,1]$ and making acos return NaN) is amplified without bound.
atan2(y,x) has derivative ${\partial }_{y}atan2=x/(x^2+y^2)$, ${\partial }_{x}atan2=-y/(x^2+y^2)$, both bounded by $1/\sqrt{x^2+y^2}$ — no blow-up as $\theta \to 0,\pi$ (where $y=\mathrm{cross}\to 0$ but $x=\mathrm{dot}\ne 0$ stays away from $0$), and no division by $|a||b|$ is needed at all. Hence atan2(|cross|, dot) is well-conditioned everywhere acos is ill-conditioned, for the same mathematical quantity. $■$

Dot and cross together

Want	Use
Angle magnitude	$atan2(|\mathrm{cross}|,\mathrm{dot})$
Signed angle	$atan2(\mathrm{cross},\mathrm{dot})$ — gives $(-\pi ,\pi ]$
Perpendicular?	$\mathrm{dot}=0$
Parallel?	$\mathrm{cross}=0$
Which side?	sign of $\mathrm{cross}$
In front or behind?	sign of $\mathrm{dot}$

The pair $(\mathrm{cross},\mathrm{dot})$ is exactly $(\mathrm{Im},\mathrm{Re})$ of the complex number $\bar{a}b$, which is why complex arithmetic works so smoothly for 2D geometry (see above).

In 3D

The dot product is unchanged: $a\cdot b=a_x{b}_x+a_y{b}_y+a_z{b}_z$, still giving perpendicularity, projection and the angle via the same law-of-cosines argument. Only the cross product changes character (scalar $\to$ vector) in 3D — see 3D Geometry.

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.

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 until output.

Proof: $\mathrm{cross}(a,b)=|a||b|\sin \theta$, the sign, and the area claim

Write $a=|a|(\cos \alpha ,\sin \alpha )$, $b=|b|(\cos \beta ,\sin \beta )$. Then
$a_x{b}_y-a_y{b}_x=|a||b|(\cos \alpha \sin \beta -\sin \alpha \cos \beta )=|a||b|\sin (\beta -\alpha ),$
and $\beta -\alpha$ is exactly the signed angle you turn through going from $a$ to $b$ (CCW positive). This is positive for a left turn ($0<\beta -\alpha <\pi$), negative for a right turn, and zero exactly when $a,b$ are parallel (same or opposite direction) — collinearity of $o,a,b$ after translating by $-o$. Its absolute value $|a||b||\sin (\beta -\alpha )|$ is base $\times$ height of the parallelogram spanned by $a,b$ (base $|a|$, height $|b|\sin (\beta -\alpha )$ the component of $b$ perpendicular to $a$), i.e. the parallelogram’s area; half of it is the triangle $o,a,b$‘s area. $■$

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 for the proof (it is the triangle-area identity above, telescoped over a fan from the origin).

Distance from a point to a line

$d(p,\overline{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);
}

This is immediate from the area identity: $|\mathrm{cross}(b-a,p-a)|$ is twice the area of triangle $abp$, which also equals $|b-a|\cdot d(p,\overline{ab})$ (base times height); divide.

For comparisons only, skip the division and the square root entirely: keep numerator squared and denominator squared separately and cross-multiply in __int128.

The sgn idiom and orientation

Most uses only need the sign, not the value:

int sgn(ll x) { return (x > 0) - (x < 0); }
int orient(P a, P b, P c) { return sgn(cross(a, b, c)); }   // +1 CCW, 0 collinear, -1 CW
 
bool onSegment(P p, P a, P b) {                // assumes p is collinear with a, b
    return dot(p - a, p - b) <= 0;
}
bool properIntersect(P a, P b, P c, P d) {      // strict crossing, not merely touching
    int o1 = orient(a, b, c), o2 = orient(a, b, d);
    int o3 = orient(c, d, a), o4 = orient(c, d, b);
    return o1 * o2 < 0 && o3 * o4 < 0;
}
bool isConvex(const vector<P>& poly) {
    int n = poly.size(), sign = 0;
    for (int i = 0; i < n; i++) {
        int o = orient(poly[i], poly[(i + 1) % n], poly[(i + 2) % n]);
        if (o == 0) continue;                  // allow collinear points
        if (sign == 0) sign = o;
        else if (sign != o) return false;
    }
    return true;
}

Working with $\{-1,0,1\}$ avoids overflow in comparisons and makes the code read as geometry rather than arithmetic. Note isConvex accepts polygons with collinear vertices; whether that counts as convex depends on the problem.

Proof: onSegment and properIntersect are correct

onSegment: given $p$ collinear with $a,b$, write $p=a+t(b-a)$ for some real $t$ (exists since collinear and, if $a\ne b$, unique). Then $p-a=t(b-a)$ and $p-b=(t-1)(b-a)$, so $\mathrm{dot}(p-a,p-b)=t(t-1)|b-a{|}^2$. Since $|b-a{|}^2>0$ (for $a\ne b$), this is $\le 0$ iff $t(t-1)\le 0$ iff $t\in [0,1]$, which is exactly ”$p$ lies on the segment $ab$”. $■$

properIntersect: $o_1\cdot o_2<0$ means $c,d$ lie strictly on opposite sides of line $ab$; by the intermediate value theorem applied to the signed distance from line $ab$ (a continuous, in fact affine, function along segment $cd$), segment $cd$ then crosses line $ab$ at some interior point of $cd$. Symmetrically $o_3\cdot o_4<0$ means segment $ab$ crosses line $cd$ at an interior point of $ab$. Both crossings refer to the same intersection point of the two lines (two non-parallel lines meet in exactly one point, and parallel lines give $o_1=o_2$ or $o_3=o_4$ automatically unless collinear, a case excluded by strict inequality), so that point is interior to both segments — a proper crossing. Conversely a proper crossing forces each pair of orientations to differ in sign, since the crossing point separates each segment’s endpoints across the other line. $■$

The in-circle predicate

The other classical predicate, needed for Delaunay triangulation: is $d$ inside the circle through $a,b,c$ (taken CCW)?

$\mathrm{sign}\left|\begin{array}{ccc}{a}_x-d_x& a_y-d_y& (a_x-d_x{)}^2+(a_y-d_y{)}^2\\ b_x-d_x& b_y-d_y& (b_x-d_x{)}^2+(b_y-d_y{)}^2\\ c_x-d_x& c_y-d_y& (c_x-d_x{)}^2+(c_y-d_y{)}^2\end{array}\right|>0⟺d\text{ is inside}.$

Degree 4 in the coordinates, so with $10^9$ inputs the determinant reaches roughly $(2\cdot 10^9{)}^2\cdot (2(2\cdot 10^9{)}^2)\approx 2\cdot 10^{40}$ — far beyond both long long and exact double. This is why Delaunay implementations need exact predicates (__int128 only pushes the bound to about $1.7\cdot 10^{38}$, still short) or heavily restricted coordinate ranges.

Proof: the in-circle determinant, via lifting to a paraboloid

Lift every point $p=(x,y)$ to $\hat{p}=(x,y,x^2+y^2)$ on the paraboloid $z=x^2+y^2$ in ${\mathbb{R}}^3$. The plane through $\hat{a},\hat{b},\hat{c}$ meets the paraboloid exactly where the circle through $a,b,c$ meets the plane $z=x^2+y^2$ — i.e. exactly on that circle, since substituting a point on the circle $|p-\text{center}{|}^2=r^2$ (a relation linear in $x^2+y^2$) into the plane equation (also linear in $x,y,z$ with $z=x^2+y^2$) gives the same linear relation. So the plane through the three lifted points is the lift of the circle through $a,b,c$: points lifted above the plane correspond to points inside the circle (their $z=x^2+y^2$ lies above where the plane says the circle’s lift sits at that $(x,y)$, which after unwinding the algebra means they are closer to the circle’s center than $r$), and points lifted below correspond to points outside.

Whether $\hat{d}$ is above or below the plane through $\hat{a},\hat{b},\hat{c}$ is exactly the sign of the $4\times 4$ orientation determinant of $\hat{a},\hat{b},\hat{c},\hat{d}$ in homogeneous form, i.e. $\det \left(\begin{array}{cccc}{a}_x& a_y& a_x^2+a_y^2& 1\\ b_x& b_y& b_x^2+b_y^2& 1\\ c_x& c_y& c_x^2+c_y^2& 1\\ d_x& d_y& d_x^2+d_y^2& 1\end{array}\right)$ (positive when $\hat{d}$ is on the same side as “up”, given $a,b,c$ CCW). Subtracting row 4 from rows 1–3 (a determinant-preserving operation) turns this into exactly the stated $3\times 3$ determinant in the shifted coordinates $a-d,b-d,c-d$. $■$

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 (e.g. comparing two cross products, or the in-circle determinant) 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.

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 that length), coplanarity of four points (scalar triple product $=0$), tetrahedron volume ($\frac{1}{6}$ the triple product). See 3D Geometry.

Why cross beats angles

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

Angular sorting

Radial sweeps, Graham scan, and visibility problems all need to sort vectors by angle. Do not use atan2 for this — sort by half-plane, then by cross product:

int half(P p) { return (p.y < 0 || (p.y == 0 && p.x < 0)) ? 1 : 0; }
int half(PD p) { return (p.y < 0 || (p.y == 0 && p.x < 0)) ? 1 : 0; }   // same split, for floating directions
bool angleLess(const P& a, const P& b) {
    int ha = half(a), hb = half(b);
    if (ha != hb) return ha < hb;
    ll c = cross(a, b);
    return c != 0 ? c > 0 : norm2(a) < norm2(b);     // tie-break collinear same-direction vectors by length
}

Exact for integer coordinates, about 5x faster than comparing atan2 values, and free of the wraparound bug at $\pm \pi$: half splits the plane into the lower half ($[\pi ,2\pi )$, i.e. angle $\ge \pi$ measuring from standard position with $-x$ axis included) and the upper half, so within a half the cross product alone totally orders the angle (no vector pair inside one half is more than $\pi$ apart, where cross’s sign stops being a reliable comparator).

Distances

Point to point, point to line, point to segment

Covered above: dist2/dist, distToLine, distToSegment. Segment-to-segment distance:

// requires segmentsIntersect from the segment-intersection toolkit, see next note
double segToSeg(P a, P b, P c, P d, bool intersects) {
    if (intersects) return 0;
    return min({distToSegment(a, c, d), distToSegment(b, c, d),
                distToSegment(c, a, b), distToSegment(d, a, b)});
}

If the segments intersect the distance is $0$; otherwise, since the distance function between two segments is convex and piecewise-linear/-quadratic with no interior critical point when they don’t cross, the minimum is attained at an endpoint of one of them against the other segment — checking all four endpoint-to-opposite-segment distances suffices. The intersection check first is essential — otherwise crossing segments would report a spurious positive distance from only checking endpoints.

Point to polygon

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

Circles

Pair	Distance
Point to circle	$||p-c|-r|$ (0 if on the circle)
Circle to circle (external)	$\max (0,|c_1-c_2|-r_1-r_2)$
Circle inside circle	$\max (0,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)$, itself convex — see Minkowski Sum.

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 }(u,v):=(x+y,x-y).$

Rotating by 45° (and scaling by $\sqrt{2}$) 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.

Proof: the rotation trick

Let $\Delta x=x_1-x_2$, $\Delta y=y_1-y_2$, and $\Delta u=\Delta x+\Delta y$, $\Delta v=\Delta x-\Delta y$. Then $\Delta u+\Delta v=2\Delta x$ and $\Delta u-\Delta v=2\Delta y$. Case on the signs of $\Delta x,\Delta y$:

• Same sign ($\Delta x\Delta y\ge 0$): $|\Delta x|+|\Delta y|=|\Delta x+\Delta y|=|\Delta u|$ (since $\Delta x,\Delta y$ don’t cancel), and $|\Delta v|=|\Delta x-\Delta y|\le |\Delta x|+|\Delta y|=|\Delta u|$, so $\max (|\Delta u|,|\Delta v|)=|\Delta u|=|\Delta x|+|\Delta y|$.
• Opposite sign: symmetric argument swaps the roles, giving $\max (|\Delta u|,|\Delta v|)=|\Delta v|=|\Delta x|+|\Delta y|$.

Either way $L_1(\Delta x,\Delta y)=L_{\infty }(\Delta u,\Delta v)$. Maximizing $L_{\infty }$ over pairs decouples into the two coordinates: ${\max }_{i,j}\max (|u_i-u_j|,|v_i-v_j|)=\max ({\max }_{i,j}|u_i-u_j|,{\max }_{i,j}|v_i-v_j|)=\max (\max u-\min u,\max v-\min v)$. $■$

In $d$ dimensions, the same idea gives ${\max }_{\text{sign pattern }s\in \{\pm 1{\}}^{d-1}}({\max }_i{\sum }_j{s}_j{x}_{i,j}-{\min }_i{\sum }_j{s}_j{x}_{i,j})$ over $2^{d-1}$ transformed coordinates (fixing the sign of the first term by symmetry).

Nearest-neighbour queries

Situation	Method
One query, $n$ points	linear scan, $O(n)$
Many queries, static points	KD-tree, $O(\log n)$ expected — see 09-kd-tree-and-spatial-structures
Closest pair among $n$	divide and conquer, $O(n\log n)$ — [[19-geometry/16-closest-pair
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 (Rule 3). Take the square root only for output, and print with enough precision (printf("%.10f") or cout << fixed << setprecision(10)).