xviii. Point Location and Point Counting

Point Location

For non-crossing segments and query points, finds for every query the first segment hit by a ray shot straight down.

vector<int> below = segmentBelow(segs, queries);   // segs: vector<pair<P,P>>, no two cross
                                                    // (shared endpoints allowed), no vertical ones;
                                                    // below[i] = index or -1; a point on a segment hits it

Complexity: $O((n+q)\log n)$.

Sweep over $x$; active segments are ordered by height, which never changes between two segments because they do not cross, so a std::set with a geometric comparator stays valid. At each $x$: answer the queries, remove the segments ending there, insert those starting there, answer again and keep the higher hit (two segments meeting at a point are never in the set together). Endpoints count as hits.

vector<int> segmentBelow(const vector<pair<P, P>>& input, const vector<P>& queries) {
    int n = input.size(), q = queries.size();
    vector<pair<P, P>> segs(input);
    for (auto& [a, b] : segs) if (b < a) swap(a, b);
    // segments in the set always share an open x-interval, so "b above the line of a" is a valid order;
    // indices >= n stand for query points
    auto less = [&](int a, int b) {
        auto pick = [&](int i) { return i < n ? segs[i] : pair{queries[i - n], queries[i - n]}; };
        auto [p1, q1] = pick(a);
        auto [p2, q2] = pick(b);
        int v = orient(p1, q1, p2) + orient(p1, q1, q2);
        if (a < n && v != 0) return v > 0;
        v = orient(p2, q2, p1) + orient(p2, q2, q1);
        if (b < n && v != 0) return v < 0;
        return a < b;
    };
    auto heightLess = [&](int a, int b, ll x) {   // height of segment a at x < height of b at x
        auto [pa, qa] = segs[a];
        auto [pb, qb] = segs[b];
        i128 na = (i128)pa.y * (qa.x - pa.x) + (i128)(qa.y - pa.y) * (x - pa.x), da = qa.x - pa.x;
        i128 nb = (i128)pb.y * (qb.x - pb.x) + (i128)(qb.y - pb.y) * (x - pb.x), db = qb.x - pb.x;
        return na * db < nb * da;
    };
    set<int, decltype(less)> active(less);
    vector<ll> xs;
    for (auto& [a, b] : segs) { xs.push_back(a.x); xs.push_back(b.x); }
    for (auto& p : queries) xs.push_back(p.x);
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    int m = xs.size();
    vector<vector<int>> starts(m), ends(m), asks(m);
    auto at = [&](ll x) { return lower_bound(xs.begin(), xs.end(), x) - xs.begin(); };
    for (int i = 0; i < n; i++) { starts[at(segs[i].first.x)].push_back(i); ends[at(segs[i].second.x)].push_back(i); }
    for (int i = 0; i < q; i++) asks[at(queries[i].x)].push_back(i);
    vector<int> res(q, -1);
    auto best = [&](int i) {   // highest active segment not above query i
        auto it = active.upper_bound(n + i);
        return it == active.begin() ? -1 : *prev(it);
    };
    for (int k = 0; k < m; k++) {
        for (int i : asks[k]) res[i] = best(i);       // segments passing through here
        for (int s : ends[k]) active.erase(s);
        for (int s : starts[k]) active.insert(s);
        for (int i : asks[k]) {                       // segments starting here
            int c = best(i);
            if (c != -1 && (res[i] == -1 || heightLess(res[i], c, xs[k]))) res[i] = c;
        }
    }
    return res;
}

Related: planar subdivision faces — label every segment with the face above it, then the face of a point is the label of the segment below (or the outer face). Vertical walls: handle with a second structure per $x$.

Proof: segmentBelow is correct

The comparator is valid. Two segments that don’t cross (no two input segments cross by assumption) have a consistent height order over their entire shared $x$-range: if segment $a$ is below $b$ at one $x$ in the overlap and above at another, they’d have to cross in between, contradicting non-crossing. less(a,b) tests this via orientation at both segments’ own endpoints relative to the other, consistent with that fixed order. A query point, treated as a degenerate zero-length “segment” {q,q}, compares against a real segment by the sign of orient(seg_p1, seg_q1, query) — above, on, or below — with the a < n / b < n branches selecting which side’s endpoints to test against (a degenerate query segment has no well-defined “orientation of its own endpoints”, so the comparator falls back to testing the real segment’s endpoints against the query instead).
Correctness of the sweep. At every compressed $x$-coordinate, the active set holds exactly the segments whose open $x$-interval contains (or touches) that $x$, correctly ordered by height (since no reordering ever happens without a crossing, which can’t occur). Querying best(i) — the predecessor of the query’s position in the ordered active set — finds the highest segment at or below the query’s height, i.e. the first one a downward ray would hit. Running this twice per query event (once before processing starts/ends at this $x$, once after) handles both “a segment that already covers this $x$” and “a segment that starts exactly at this $x$” without missing either, and comparing the two candidates by heightLess (exact height via i128 to avoid overflow in the cross-multiplied comparison) picks the genuinely higher of the (at most two) candidates, since a segment ending exactly at the query’s $x$ and one starting there cannot be simultaneously in the active set (removing happens before the first query check, inserting after) — the explicit before/after comparison recovers the correct answer when the true hit is exactly at a segment’s endpoint. $■$

Tested against brute force: for every query, scan all segments whose $x$-range contains the query’s $x$, compute each one’s exact height there (as a fraction, compared cross-multiplied to avoid floating point), and take the highest one at or below the query — on random sets of non-crossing segments (built by generating random segments and discarding any crossing pair) and random query points, including queries exactly on a segment and exactly at a segment endpoint.

Points in Triangle

Number of points of a set $B$ strictly inside the triangle $A_i{A}_j{A}_k$ for many queries over vertices from a set $A$.

TrianglePointCounter tc(A, B);         // vector<P>; duplicates / collinear points allowed
int c = tc.count(i, j, k);             // 0 for degenerate triangles

Complexity: $O(n(n+m)\log (n+m))$ build and $O(n^2)$ memory ($n=|A|$, $m=|B|$); $O(1)$ per query.

Lexicographic $(x,y)$ order acts as an infinitesimal rotation of the $x$-order, so every point has its own “column” with no ties to special-case. below[i][j] = $B$ points strictly between $A_i$ and $A_j$ in that order and strictly below segment $i\text{-}j$ (found via an angular sweep around $A_i$ with a Fenwick tree over $B$‘s order); onSeg[i][j] = $B$ points strictly on that segment. With $a<b<c$ in lex order: if $b$ is above line $a$-$c$, the answer is $\mathrm{below}[a][b]+\mathrm{below}[b][c]-\mathrm{below}[a][c]-\mathrm{onSeg}[a][c]$; otherwise $\mathrm{below}[a][c]-\mathrm{below}[a][b]-\mathrm{below}[b][c]-\mathrm{onSeg}[a][b]-\mathrm{onSeg}[b][c]-\mathrm{same}[b]$ (points of $B$ equal to $A_b$). (Library Checker “Count Points in Triangle”.)

struct TrianglePointCounter {
    int n;
    vector<P> A;
    vector<vector<int>> below, onSeg;   // A[i] <lex A[j]: B points lex-between, strictly below / on segment i-j
    vector<int> same;                   // B points equal to A[i]
 
    TrianglePointCounter(const vector<P>& a, vector<P> B)
        : n(a.size()), A(a), below(n, vector<int>(n, 0)), onSeg(n, vector<int>(n, 0)), same(n, 0) {
        sort(B.begin(), B.end());
        int m = B.size();
        auto rankOf = [&](const P& p) { return int(lower_bound(B.begin(), B.end(), p) - B.begin()); };
        vector<int> fen(m + 1);
        struct Item { P d; int type, id; };   // type 0 = vertex A[id], 1 = point B[id]
        for (int i = 0; i < n; i++) {
            same[i] = int(upper_bound(B.begin(), B.end(), A[i]) - B.begin()) - rankOf(A[i]);
            vector<Item> items;
            for (int j = 0; j < n; j++) if (A[i] < A[j]) items.push_back({A[j] - A[i], 0, j});
            for (int r = upper_bound(B.begin(), B.end(), A[i]) - B.begin(); r < m; r++) items.push_back({B[r] - A[i], 1, r});
            sort(items.begin(), items.end(), [&](const Item& x, const Item& y) {   // by angle, then distance
                ll c = cross(x.d, y.d);
                if (c != 0) return c > 0;
                if (x.d != y.d) return x.d < y.d;
                return x.type < y.type;
            });
            fill(fen.begin(), fen.end(), 0);
            for (int s = 0; s < (int)items.size();) {
                int e = s;
                while (e < (int)items.size() && cross(items[s].d, items[e].d) == 0) e++;
                int seen = 0;   // B points of this ray closer than the current item
                for (int t = s; t < e; t++) {
                    if (items[t].type == 1) { seen++; continue; }
                    int j = items[t].id, cnt = 0;
                    for (int x = rankOf(A[j]); x > 0; x -= x & -x) cnt += fen[x];
                    below[i][j] = cnt; onSeg[i][j] = seen;
                }
                for (int t = s; t < e; t++)
                    if (items[t].type == 1) for (int x = items[t].id + 1; x <= m; x += x & -x) fen[x]++;
                s = e;
            }
        }
    }
 
    int count(int i, int j, int k) const {
        array<int, 3> v = {i, j, k};
        sort(v.begin(), v.end(), [&](int x, int y) { return A[x] < A[y]; });
        auto [a, b, c] = v;
        if (A[a] == A[b] || A[b] == A[c]) return 0;
        ll side = cross(A[a], A[c], A[b]);
        if (side == 0) return 0;
        if (side > 0) return below[a][b] + below[b][c] - below[a][c] - onSeg[a][c];   // b above line a-c
        return below[a][c] - below[a][b] - below[b][c] - onSeg[a][b] - onSeg[b][c] - same[b];
    }
};

Proof: TrianglePointCounter

below[i][j]/onSeg[i][j]. Fixing $i$, sweep a ray around $A_i$ by angle (via the angular sort of direction vectors d), processing vertices $A_j$ (with $A_i{<}_{\text{lex}}{A}_j$) and points of $B$ lexicographically after $A_i$ together. For a fixed direction (a maximal run of equal-angle items, [s,e)), every $B$-point on that exact ray closer to $A_i$ than $A_j$ has already been inserted into the Fenwick tree by the time $A_j$ is processed (processed in increasing distance along the same ray within the run, since ties by x.d — the un-normalized direction vector, whose magnitude is monotone with distance along a fixed ray — are broken by actual coordinate order) — these are exactly the onSeg[i][j] points (strictly on segment $A_i{A}_j$, since both the direction and the “closer” ordering match). The Fenwick tree query at that moment counts $B$-points at smaller angle (already fully processed in earlier rays) restricted to rank $\le \mathrm{rank}(A_j)$ in $B$‘s own sorted order — which, combined with the angular restriction, counts exactly the points strictly between ray $A_i{A}_j$ (exclusive) and the lexicographic-order boundary, i.e. strictly below segment $A_i{A}_j$ in the sense needed for the inclusion-exclusion formula (this is the standard “count points below a chord via a rotating sweep + Fenwick tree” technique, the same structural idea as angular sweeps elsewhere in this chapter).
count. With $a{<}_{\text{lex}}b{<}_{\text{lex}}c$, the triangle $abc$‘s interior is the region between the two chains $a\to b\to c$ and $a\to c$ (in lex-$x$ order, exactly like the monotone-chain upper/lower split). If $b$ is above line $a$-$c$: points below $a$-$b$ union below $b$-$c$, minus points below $a$-$c$ (double counted, since both chains agree below $a$-$c$) minus points on segment $a$-$c$ itself (not interior, but included in “below $a$-$c$” by the strict inequality direction) gives exactly the interior count — the stated formula. The symmetric case ($b$ below $a$-$c$) subtracts analogously, and $-\mathrm{same}[b]$ additionally removes $B$-points coincident with vertex $b$ that would otherwise be miscounted by the boundary bookkeeping in that orientation. Degenerate triangles (side==0, or two vertices lexicographically equal as points) correctly return 0 since they enclose no area. $■$

Tested against brute force: build with small random $A,B$ (duplicates and collinear points included), then for every triple $(i,j,k)$ count $B$-points with `inTriangle` directly (checking strict interior, i.e. excluding the boundary) and compare.

Max Collinear

Largest number of the given integer points lying on one line (duplicates count separately).

int best = maxCollinear(pts);   // vector<P>

Complexity: $O(n^2\log n)$. For every anchor $i$, normalise the direction to each other point (divide by the gcd, fix the sign) and count equal directions; copies of the anchor join every line through it. For $n\sim 10^5$ with an answer known to be large ($\ge n/k$), pick random anchors instead (randomised, $O(kn\log n)$).

int maxCollinear(const vector<P>& pts) {
    int n = pts.size(), best = min(n, 2);
    for (int i = 0; i < n; i++) {
        map<pair<ll, ll>, int> dirs;
        int same = 0, top = 0;
        for (int j = 0; j < n; j++) {
            if (j == i) continue;
            ll dx = pts[j].x - pts[i].x, dy = pts[j].y - pts[i].y;
            if (dx == 0 && dy == 0) { same++; continue; }
            ll g = __gcd(llabs(dx), llabs(dy));
            dx /= g; dy /= g;
            if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; }
            top = max(top, ++dirs[{dx, dy}]);
        }
        best = max(best, 1 + same + top);
    }
    return n == 0 ? 0 : best;
}

Proof: maxCollinear

Fixing anchor $A_i$, every other point $A_j$ lies on the line through $A_i$ in direction $A_j-A_i$; two points $A_j,A_k$ are collinear with $A_i$ iff their directions from $A_i$ are parallel, i.e. the same after canonicalising (dividing by the gcd and fixing a sign convention, exactly `canonicalDir`‘s construction). So the largest group of points collinear with $A_i$ (through $A_i$) is the most common canonical direction (top), plus the points exactly coincident with $A_i$ (same, trivially collinear with any line through $A_i$), plus $A_i$ itself. Taking the max over all anchors finds the true maximum, since any maximal collinear set of size $\ge 2$ contains at least one point, and fixing that point as the anchor correctly counts the whole set (every line with $\ge 1$ point is found when that point is the anchor, so in particular the best line is found when any of its own points is the anchor). $■$

Tested against brute-force $O(n^3)$ (every pair of points defines a line; count how many of the remaining points are collinear with it via orient, take the max) on random point sets including duplicates and sets with many points on one line.

Dobkin-Kirkpatrick

A multi-resolution representation of a convex polytope that answers many queries in $O(\log n)$ — polytope separation, extreme point in a direction, ray shooting, and distance between two convex polytopes.

The structure

Build a sequence of nested convex polytopes $P=P_0\supset P_1\supset \cdots \supset P_k$, where each $P_{i+1}$ is obtained from $P_i$ by:

1. finding an independent set of vertices (no two adjacent) with bounded degree — a constant fraction of the vertices, since planar/3-polytope graphs have bounded average degree;
2. deleting them and re-triangulating the resulting holes.

Each step removes a constant fraction of the vertices, so: the hierarchy has $O(\log n)$ levels; the total size across all levels is $O(n)$ (a geometric series); the coarsest level $P_k$ is a constant-size polytope (a tetrahedron).

How queries use it

Answer the query on the tiny top-level polytope in $O(1)$, then refine downwards: at each level, the answer on $P_{i+1}$ is within $O(1)$ combinatorial distance of the answer on $P_i$, because only an independent set of vertices was reinserted. So each level costs $O(1)$ and there are $O(\log n)$ levels, giving $O(\log n)$ total.

Query	Time
Is a point inside the polytope?	$O(\log n)$
Extreme vertex in direction $\vec{d}$	$O(\log n)$
Intersection of a line with the polytope (ray shooting)	$O(\log n)$
Separating plane between two convex polytopes	$O({\log }^{2}n)$
Distance between two convex polytopes	$O({\log }^{2}n)$
Tangent lines/planes from an external point	$O(\log n)$

This is genuinely intricate to implement (maintaining the independent-set hierarchy and the per-level refinement maps); like Kirkpatrick-Seidel, it is presented here for the technique rather than as code to hand-roll in a contest.

The 2D analogue you will actually use

In two dimensions, all of this collapses into something much simpler: a convex polygon’s vertices, in order, form a cyclically unimodal sequence with respect to any linear objective (proved in Convex Polygon Queries). So:

• extreme point in a direction $\to$ extremeVertex, $O(\log n)$;
• point in convex polygon $\to$ inConvex, $O(\log n)$;
• tangents from a point $\to$ convexTangents, $O(\log n)$;
• line-polygon intersection $\to$ lineHullIntersection, $O(\log n)$.

These are the 20-line routines contest problems actually need. The Dobkin-Kirkpatrick hierarchy is the machinery required to get the same guarantees in 3D, where “binary search on the boundary” no longer makes sense.

Complexity

Construction $O(n)$; space $O(n)$; query $O(\log n)$ or $O({\log }^{2}n)$.

The general technique

Building an $O(\log n)$-level hierarchy where each level is a constant-factor coarsening, then refining the answer level by level, is a broadly reusable idea:

• Sparse tables and binary lifting — the same doubling in a different dress.
• Fractional cascading — reuse a binary search across many sorted lists.
• Borůvka-style contraction — geometric shrinking in graph algorithms.
• Level-of-detail meshes in graphics — literally this structure.

Variants / Use Cases

• Convex Hull — build the polytope first.
• Seidel’s LP — the other route to low-dimensional geometric optimisation.
• GJK algorithm — the practical collision-detection method for convex bodies; a different technique, the same problem.
• 3D Geometry.