whoashish's cp notes

Geometry Basics

4 min read

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:

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 , a cross product reaches — just inside long long, but a squared distance times another squared distance is not. Use __int128 when in doubt.

Rule 2: one epsilon, used consistently

const double EPS = 1e-9;
int sgn(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 relative to the coordinate magnitude: with values around and double’s 15-16 significant digits, absolute precision is about — so is too small and will misclassify. Use there, or switch to long double, or rescale.

The point struct

struct P {
    long long 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*(long long 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; }
};
 
long long cross(const P& a, const P& b) { return a.x * b.y - a.y * b.x; }
long long dot(const P& a, const P& b)   { return a.x * b.x + a.y * b.y; }
long long cross(const P& o, const P& a, const P& b) { return cross(a - o, b - o); }
long long norm2(const P& a) { return dot(a, a); }              // squared length
double abs_(const P& a) { return sqrt((double)norm2(a)); }

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

Rule 3: compare by squared distance

if (norm2(a - p) < norm2(b - p))          // exact, integer

Never take a square root just to compare. Same for “is this distance ”: compare .

Rule 4: use atan2, and beware of it

gives the angle in and handles all four quadrants. But sorting by atan2 is slow and imprecise. Sort by half-plane plus cross product instead:

int half(const P& p) { return (p.y < 0 || (p.y == 0 && p.x < 0)) ? 1 : 0; }
bool angleLess(const P& a, const P& b) {
    int ha = half(a), hb = half(b);
    if (ha != hb) return ha < hb;
    return cross(a, b) > 0;                    // exact, integer
}

This is the standard angular sort, and it is exact for integer input.

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
  • or
  • 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 conventions

Use counter-clockwise positive throughout: means is counter-clockwise from . Polygons are stored 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.

See also: Cross Product · Orientation Test · Floating Point

Graph View