Proficient.
Put your skills to the test.

Problem summary

Find the maximum number of the given segments that one vertical or horizontal infinite line can intersect. Touching a segment endpoint counts as an intersection.

Constraints

0<N<300000; every coordinate is an integer in [−10^8,10^8].

Worked example

Original statement sample.

4
-2 -2 2 2
2 1 2 4
1 5 3 5
-4 0 0 -4

3

Solution analysis

1. A vertical line x=c intersects a segment exactly when c lies in its closed x projection [min(x1,x2),max(x1,x2)]. Thus count the greatest overlap of these intervals. Repeat with y projections for horizontal lines.
2. Create a +1 event at each interval start and a −1 event at its end. At the same coordinate process starts before ends, because intervals are closed and endpoint contacts count. The maximum running count is the greatest overlap.
3. At x=2 in the sample, the first, second and third segments are all intersected. The fourth ends at x=0, so it does not contribute there. A vertical or horizontal sweep finds the maximum 3 without computing any segment–segment intersections.

Why it works

Projection onto an axis preserves exactly the existence of an intersection with a perpendicular line. Between consecutive endpoint coordinates, the set of intersected segments is constant. At an endpoint, start-before-end ordering evaluates the complete closed-interval overlap, so the sweep checks every possible maximum.

Watch out. Do not remove ending intervals before adding starting ones at the same coordinate. Vertical, horizontal and degenerate segments work naturally as zero-length projection intervals.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int maximumOverlap(vector<pair<int,int>>&events){
    sort(events.begin(),events.end(),[](auto a,auto b){
        if(a.first!=b.first){
            return a.first<b.first;
        }
        return a.second>b.second;
    });
    int active=0;
    int answer=0;
    for(auto event:events){
        // At an endpoint, starts are counted before ends are removed.
        active+=event.second;
        answer=max(answer,active);
    }
    return answer;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<pair<int,int>>xEvents,yEvents;
    xEvents.reserve(2*n);
    yEvents.reserve(2*n);
    for(int i=0;i<n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        xEvents.push_back({min(x1,x2),1});
        xEvents.push_back({max(x1,x2),-1});
        yEvents.push_back({min(y1,y2),1});
        yEvents.push_back({max(y1,y2),-1});
    }
    cout<<max(maximumOverlap(xEvents),maximumOverlap(yEvents))<<'\n';
}