Sweep Line for Orthogonal Segment Intersections

Horizontal–vertical intersections are a useful special case with a simple sweep invariant. When a vertical segment is queried at x, every active horizontal segment spans that x-coordinate. A Fenwick tree over compressed horizontal heights counts how many active heights lie in the vertical segment’s closed y-range. The program counts segment pairs, not unique geometric crossing locations, and includes endpoint touches.

Prerequisites: Sweep Line Fundamentals; Fenwick Tree; binary search.

Build the idea

1. Create three event kinds

   A horizontal segment from (l,y) to (r,y) enters at min(l,r) and exits at max(l,r). A vertical segment at x with range [lo,hi] creates a query event. At equal x, process entries first, queries second and exits last. Therefore a horizontal segment is active for both of its endpoints. Zero-length horizontal or vertical segments remain valid typed point segments.

2. Compress y-coordinates

   Only horizontal heights ever receive updates, so collect, sort and deduplicate those y-values. Each coordinate becomes a Fenwick index, but its order is preserved. Multiple distinct horizontal segments at the same height add multiple units to the same index; using a boolean would lose multiplicity. A vertical query can use arbitrary endpoints not present in the compression.

   $$\mathrm{count}[\mathrm{lo},\mathrm{hi}]=\mathrm{prefix}(\mathrm{upper}\_\mathrm{bound}(\mathrm{hi}\left)\right)-\mathrm{prefix}(\mathrm{lower}\_\mathrm{bound}(\mathrm{lo}\left)\right)$$

3. Translate an inclusive range query

   lower_bound(lo) counts compressed coordinates strictly below lo. upper_bound(hi) counts coordinates at most hi. Subtract those Fenwick prefix sums to obtain the closed range count. The Fenwick prefix function takes a count of coordinates, while add takes a zero-based compressed index and shifts internally. Keeping these conventions explicit avoids off-by-one errors.

4. Trace the sample

   Horizontal segments are x∈[0,4] at y=1 and x∈[2,6] at y=3. A vertical segment x=2,y∈[0,4] meets both. A second at x=4,y∈[1,1] meets the first at its endpoint, contributing one more. Total segment-pair intersections are 3. Entry-before-query and query-before-exit are essential for both boundary cases.

5. Separate counting from reporting

   Each query returns a number in O(log n), so counting can avoid visiting all crossings even when there are Θ(hv). To report every intersecting pair, maintain active items in an ordered structure keyed by (y,id), iterate the queried height interval and output each hit. That reporting variant costs O(n log n+K) including output K; it is not the Fenwick counting program shown here.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
struct Event{
    long long x,y1,y2;
    int type;
}; // 0 add, 1 query, 2 remove: closed endpoints.
struct Fenwick{
    std::vector<int>bit;
    explicit Fenwick(int n):bit(n+1){
    }
    void add(int i,int d){
        for(++i;i<(int)bit.size();i+=i&-i){
            bit[i]+=d;
        }
    }
    int prefix(int count){
        int s=0;
        for(int i=count;i>0;i-=i&-i){
            s+=bit[i];
        }
        return s;
    }
};
int main(){
    int h,v;
    std::cin>>h>>v;
    std::vector<long long>ys;
    std::vector<Event>events;
    for(int i=0;i<h;++i){
        long long l,r,y;
        std::cin>>l>>r>>y;
        if(l>r){
            std::swap(l,r);
        }
        ys.push_back(y);
        events.push_back({l,y,y,0});
        events.push_back({r,y,y,2});
    }
    for(int i=0;i<v;++i){
        long long x,l,r;
        std::cin>>x>>l>>r;
        if(l>r){
            std::swap(l,r);
        }
        events.push_back({x,l,r,1});
    }
    std::sort(ys.begin(),ys.end());
    ys.erase(std::unique(ys.begin(),ys.end()),ys.end());
    std::sort(events.begin(),events.end(),[](Event a,Event b){
        return a.x!=b.x?a.x<b.x:a.type<b.type;
    });
    Fenwick active(ys.size());
    long long answer=0;
    // Active Fenwick values count horizontal segments, including multiplicity.
    for(Event e:events){
        if(e.type==1){
            int left=std::lower_bound(ys.begin(),ys.end(),e.y1)-ys.begin(),
                right=std::upper_bound(ys.begin(),ys.end(),e.y2)-ys.begin();
            answer+=active.prefix(right)-active.prefix(left);
        }
        else{
            active.add(std::lower_bound(ys.begin(),ys.end(),e.y1)-ys.begin(),e.type==0?1:-1);
        }
    }
    std::cout<<answer<<'\n';
}

Complexity analysis

Counting: O((h+v) log(h+v+1)) time, O(h+v) event/compression storage and O(h) Fenwick storage. The answer can be h·v≤10^10, so use long long. Reporting with a suitable ordered active set takes O(n log n+K), distinct from counting.

Example input and output

Read h v (0..100000 each). Then h horizontal rows l r y, and v vertical rows x lo hi. Integer coordinates within ±10^6; endpoints are closed, multiplicities count separately. Print the total intersecting horizontal–vertical pairs.

Input

2 2
0 4 1
2 6 3
2 0 4
4 1 1

Output

3

The first vertical meets both horizontals; the second meets the first at (4,1).

Practical applications

Use for grid drawings, wire crossings and offline range-count questions. A Fenwick tree handles counts; reporting requires access to segment IDs. Arbitrary slanted segments need a more complicated sweep and robust ordering.

Check your understanding

What tie order counts closed endpoint contacts?

Put it into practice

Test several identical horizontal segments and a vertical through their endpoint.