⚙️AlgorithmIntermediate

Line Sweep

Key Points

•
Line sweep (plane sweep) is a technique that processes geometric objects by moving an imaginary line and handling events in sorted order.
•
You maintain an active set of objects currently intersecting the sweep line and update it only at discrete event positions.
•
Sorting events costs O(n $lo g$ n), and each balanced-tree update on the active set costs O( $lo g$ n).
•
Classic applications include segment intersection (Bentley–Ottmann), closest pair of points, and rectangle union area.
•
Choosing the right event types and a correct tie-breaking order is crucial for correctness.
•
Robust implementations require careful handling of degeneracies like shared endpoints, vertical segments, and collinear overlaps.
•
Coordinate compression and segment trees often turn 2D sweeps into efficient O(n $lo g$ n) solutions.
•
Floating-point precision issues can break geometric predicates; prefer integer arithmetic when possible.

Prerequisites

→Sorting and tie-breaking — Events must be processed in a strict order; correct tie-breaking affects correctness at shared coordinates.
→Balanced binary search trees — Active sets for sweeps often require O(log n) insert/erase and neighbor queries.
→Segment trees and Fenwick trees — Measure and range-count sweeps rely on fast range updates and queries.
→Coordinate compression — Compressing coordinates keeps segment trees/BITs small and efficient over large ranges.
→Geometric predicates (orientation, intersection) — Robustly detecting turns and intersections is essential for segment-based sweeps.
→Floating-point vs integer arithmetic — Understanding precision and robustness guides safe implementation choices.
→Algorithmic complexity — Analyzing O(n log n) behavior and event counts clarifies why sweeps are efficient.
→Divide and conquer basics — Closest pair has both D&C and sweep variants; understanding either helps the other.

Detailed Explanation

Tap terms for definitions

01Overview

Line sweep (also called plane sweep) is an algorithmic paradigm used to solve many geometric problems efficiently. Imagine moving a vertical or horizontal line across the plane. You process objects (points, segments, rectangles) in the order that they are first encountered by the line. At certain x (or y) positions called events, the set of objects that intersect the sweep line changes. Between events, the combinatorial structure stays the same, so you only need to update the active set at these event positions. The active set is typically stored in a balanced binary search tree, often ordered by the y-coordinate where objects intersect the sweep line. The power of line sweep comes from two facts: (1) sorting events is O(n \log n), and (2) each insertion, deletion, or neighbor check in the active structure is O(\log n), yielding near-optimal overall performance. This approach underlies classic algorithms: detecting/enumerating line segment intersections (Bentley–Ottmann), computing the union area of rectangles with a segment tree over y, counting intersections between axis-aligned segments, and even the closest pair of points in the plane using a sliding window ordered by y. The key design choices are defining the right events, maintaining an appropriate status structure, and establishing correct tie-breaking rules that ensure every necessary update is performed exactly when needed.

02Intuition & Analogies

Picture a street sweeper truck that moves from the left side of a city map to the right. Buildings, roads, and parks don’t change while the truck moves between intersections; the only times decisions are made are at intersections where streets begin or end. Similarly, in line sweep you move an imaginary vertical line across geometric objects. You only need to stop at special locations (events) where something meaningful happens: an object starts to intersect the sweep line, stops intersecting it, or two objects cross. Between these stops, nothing changes in the relative ordering of objects along the sweep line, so there’s no reason to recompute anything. Another analogy: think of checking people into and out of a concert venue. Each person contributes +1 when they enter and -1 when they leave. If you process the entry/exit times in order, you can maintain the current crowd size with a running total. That’s a 1D line sweep on the time axis. In 2D geometry, we generalize this: a rectangle contributes a y-interval when your sweep line crosses its left edge and removes the interval at its right edge. Keeping track of which y-positions are currently covered (via a segment tree) lets you compute the total covered length at any x; multiplying by the horizontal distance to the next event gives you an area contribution. For segment intersections, you keep the segments that currently cross the sweep line in order by their y at the sweep x, and only neighbor pairs can start or stop intersecting as you move—so you check just those pairs rather than all pairs. This is why sweeps are both intuitive and fast.

03Formal Definition

A line sweep algorithm chooses an orientation (typically vertical line

x = co n s t

) and defines an ordered set of events E = {

e_{1}

e_{2}

\dots

e_{m}

} sorted by an event key (usually x, then tie-breaks). It maintains a sweep status S(x), an ordered structure representing all objects intersecting the sweep line at position x. Updates to S occur only at event positions; between events, S is assumed to be combinatorially invariant. For each event

e_{i}

at coordinate

x_{i}

, the algorithm performs a bounded number of updates to S (insertions, deletions, local neighbor checks, or range updates), possibly generating additional events (e.g., intersection points) to be processed later. If S is maintained in a balanced binary search tree or a segment tree, each update takes O(

lo g

n) time. When the algorithm terminates, it has computed the desired global property (e.g., number of intersections, union area, or minimum distance). For example, in rectangle union area, events are vertical edges at x-coordinates; S(x) is a segment tree storing the union length of y-intervals currently active; and the area is accumulated as

\sum_{i}

(

x_{i + 1}

x_{i}

)

\cdot

x_{i}

), where L(

x_{i}

) is the covered y-length at

x_{i}

. In Bentley–Ottmann, events include segment endpoints and discovered intersection points; S(x) is a BST of segments ordered by their y at x; and only adjacent segments in S can generate new intersections.

04When to Use

Use a line sweep when objects can be processed in a natural left-to-right (or bottom-to-top) order and local changes fully capture global behavior. Common cases include: (1) union/measure problems where integrating a 1D measure across the other dimension works, such as rectangle union area, perimeter, or covered length; (2) intersection problems where potential interactions are localized to neighbors in a well-ordered status structure, such as detecting or enumerating line segment intersections, counting intersections between axis-aligned segments, or computing trapezoidal decompositions; (3) proximity problems with locality constraints, such as the closest pair of points using a sliding window ordered by y; (4) scheduling/aggregation on a line (1D), like counting maximum overlap of intervals, cumulative active weight over time, or checking resource feasibility. Line sweep shines when n is large and a naive O(n^2) pairwise approach is too slow. It is also a great fit when you can define a small, finite set of event types with predictable updates, and when balanced tree or segment tree data structures give you O(\log n) updates. Avoid line sweep if events are ill-defined, the ordering is unstable (e.g., requires constantly re-sorting with heavy numeric instability), or if the active set needs global rather than local updates at each step.

⚠️Common Mistakes

• Ignoring tie-breaking: Failing to specify a total order for events leads to inconsistent handling of corner cases (e.g., start vs. end at the same x). Always decide which to process first (typically starts before queries before ends, or problem-specific rules) and document it. • Floating-point pitfalls: Using doubles for orientation tests or y-at-x comparisons can produce wrong orderings near degeneracies. Prefer integer arithmetic (64-bit) for predicates when input is integral. If doubles are necessary, use epsilons and consistent comparisons. • Status comparator depending on a mutable global: Using std::set with a comparator that changes as x advances is technically undefined behavior in C++. Many competitive programmers do it anyway, but safer approaches are to restrict to axis-aligned problems, rebuild when needed, or carefully ensure consistency and only change x between operations. For teaching, consider tasks where the status is a segment tree or Fenwick tree keyed by fixed coordinates. • Missing neighbor checks: In segment-intersection sweeps, after inserting/removing a segment you must check both new neighbors for potential intersections and schedule intersection events; otherwise, you can miss crossings. • Incorrect event generation for closed vs. open intervals: Decide whether intervals are [l, r), [l, r], etc. Inconsistent handling can double-count or miss contributions at boundaries. • Not compressing coordinates: For large coordinate ranges, failing to compress y-values makes segment trees huge and slow. Coordinate compression is simple and often essential. • Over-updating segment trees: When storing covered length in rectangle union, you must store both cover count and the covered length of a node’s segment; naive toggling without counts fails on overlapping rectangles.

Key Formulas

Bentley–Ottmann Complexity

O (n lo g n + k lo g n)

Explanation: Processing n segments yields O(n log n) for sorting and O(log n) per event/status update. Reporting k intersections adds a factor of O(k log n) to insert intersection events and handle neighbor swaps.

Orientation (Cross Product)

orient (a, b, c) = (b_{x} - a_{x}) (c_{y} - a_{y}) - (b_{y} - a_{y}) (c_{x} - a_{x})

Explanation: This signed area determines if c lies to the left (>0), right (<0), or is collinear (=0) with directed segment ab. It is fundamental for robust geometric predicates.

Euclidean Distance

d (p, q) = (p_{x} - q_{x})^{2} + (p_{y} - q_{y})^{2}

Explanation: Distance between two points in the plane. In closest pair algorithms, you often compare squared distances to avoid square roots.

Rectangle Union via Sweep

A re a = i = 1 \sum m - 1 (x_{i + 1} - x_{i}) \cdot L (x_{i})

Explanation: With vertical sweep events at sorted $x_{i}$ , L( $x_{i}$ ) is the covered y-length maintained by a segment tree. Multiplying by the slab width accumulates area.

Sorting Lower Bound

i = 1 \sum n lo g i = Θ (n lo g n)

Explanation: Any comparison-based sort takes at least O(n log n). Since line sweep begins with sorting events, this often dominates the runtime.

Segment Tree Operation Cost

T_{se g t ree o p} = O (lo g m)

Explanation: Each range update or query on a segment tree over m leaves is logarithmic. Rectangle union sweeps repeatedly perform these operations.

1D Active Count

I = x = e v e n t s \sum (adds) - (removes)

Explanation: For interval overlaps on a line, sweeping with +1 at starts and -1 at ends maintains the current active count. The maximum over the sweep is the peak overlap.

Complexity Analysis

Most line sweep algorithms begin by sorting O(n) events, costing O(n

lo g

n). After that, the performance hinges on the status structure. If the active set is a balanced BST (red-black tree via std::set) and each event triggers O(1) insertions/deletions with O(1) neighbor checks, the per-event cost is O(

lo g

n). For intersection enumeration (Bentley–Ottmann), discovered intersections are themselves events, adding k events for k intersections, which yields O((n + k)

lo g

n) total time. Space usage is typically O(n + k): O(n) for the event queue and status, plus O(k) to store reported intersections. For measure problems like rectangle union area, we maintain a segment tree over compressed y-coordinates. Building the tree is O(m), where m is the number of distinct y-values (O(n)). Each vertical edge triggers a range add or remove in O(

lo g

m), and there are O(n) such edges, so the total is O(n

lo g

n) with O(n) space for the tree and events. For 1D interval overlap, sorting endpoints is O(n

lo g

n), and the sweep itself is O(n) time and O(n) space for events. Closest pair with a sweep uses a set ordered by y and a sliding window constrained by the current best distance. Each point is inserted and removed at most once, so the set operations are O(

lo g

n) per point. The inner candidate scan checks a constant number of neighbors on average, leading to O(n

lo g

n) time and O(n) space. In practice, the leading constants depend on robust tie-breaking, coordinate compression, and careful handling of degeneracies; nonetheless, O(n

lo g

n) is the typical, near-optimal bound for sweep-based solutions.

Code Examples

1D Line Sweep: Maximum Overlap of Intervals

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // This program reads n intervals [l, r) and computes the maximum number
5 // of overlapping intervals and one position where this maximum occurs.
6 // We use a classic 1D sweep: +1 at start, -1 at end, sorted by coordinate.
7 
8 int main() {
9     ios::sync_with_stdio(false);
10     cin.tie(nullptr);
11 
12     int n; 
13     if (!(cin >> n)) return 0;
14     vector<pair<long long,int>> events; // (x, delta)
15     events.reserve(2*n);
16     for (int i = 0; i < n; ++i) {
17         long long l, r; cin >> l >> r; 
18         // We'll treat intervals as [l, r): start adds, end removes.
19         events.push_back({l, +1});
20         events.push_back({r, -1});
21     }
22     // Tie-breaking: at the same x, process +1 before -1 to treat [l, r) correctly
23     sort(events.begin(), events.end(), [](auto &a, auto &b){
24         if (a.first != b.first) return a.first < b.first;
25         return a.second > b.second; // +1 before -1
26     });
27 
28     long long curr = 0, best = 0; 
29     long long best_pos = events.empty() ? 0 : events[0].first;
30 
31     for (size_t i = 0; i < events.size(); ) {
32         long long x = events[i].first;
33         // apply all deltas at this x
34         while (i < events.size() && events[i].first == x) {
35             curr += events[i].second;
36             ++i;
37         }
38         if (curr > best) {
39             best = curr;
40             best_pos = x; // any point in [x, next_x) achieves 'best'
41         }
42     }
43 
44     cout << best << " " << best_pos << "\n";
45     return 0;
46 }
47

We convert each interval [l, r) into two events: +1 at l and -1 at r. Sorting all events by coordinate and applying deltas accumulates the active count. The maximum of this running total is the peak overlap. Processing +1 before -1 at equal x ensures [l, r) semantics and avoids double-counting.

Time: O(n log n)Space: O(n)

Rectangle Union Area via Vertical Sweep + Segment Tree

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute the area of union of axis-aligned rectangles.
5 // Input: n, then n lines: x1 y1 x2 y2 with x1 < x2, y1 < y2 (64-bit ints allowed).
6 // Approach: vertical sweep over rectangle edges; maintain covered y-length using a segment tree
7 // built over compressed y-coordinates. Each edge performs a range add (+1 for left edge, -1 for right).
8 
9 struct Node {
10     int cover = 0;          // how many intervals cover this segment
11     long long covered = 0;  // covered length in this segment (using original y-units)
12 };
13 
14 struct SegTree {
15     int n; // number of elementary intervals (m-1 if m distinct y's)
16     vector<Node> st;
17     vector<long long> ys; // coordinates (size m)
18     SegTree(const vector<long long>& coords) {
19         ys = coords;
20         n = (int)ys.size() - 1; // n elementary segments
21         st.assign(4*n+4, {});
22     }
23     void pull(int p, int l, int r) {
24         if (st[p].cover > 0) {
25             st[p].covered = ys[r+1] - ys[l]; // fully covered
26         } else if (l == r) {
27             st[p].covered = 0;
28         } else {
29             st[p].covered = st[p<<1].covered + st[p<<1|1].covered;
30         }
31     }
32     void update(int p, int l, int r, int ql, int qr, int delta) {
33         if (ql > r || qr < l) return;
34         if (ql <= l && r <= qr) {
35             st[p].cover += delta;
36             pull(p, l, r);
37             return;
38         }
39         int m = (l + r) >> 1;
40         update(p<<1, l, m, ql, qr, delta);
41         update(p<<1|1, m+1, r, ql, qr, delta);
42         pull(p, l, r);
43     }
44     // External call with [y1, y2) in original coords
45     void add_interval(long long y1, long long y2, int delta) {
46         int l = int(lower_bound(ys.begin(), ys.end(), y1) - ys.begin());
47         int r = int(lower_bound(ys.begin(), ys.end(), y2) - ys.begin()) - 1; // inclusive index of elementary segments
48         if (l <= r) update(1, 0, n-1, l, r, delta);
49     }
50     long long covered_length() const { return st[1].covered; }
51 };
52 
53 struct Edge { long long x, y1, y2; int type; }; // type: +1 add, -1 remove
54 
55 int main(){
56     ios::sync_with_stdio(false);
57     cin.tie(nullptr);
58 
59     int n; if(!(cin >> n)) return 0;
60     vector<Edge> edges; edges.reserve(2*n);
61     vector<long long> ys; ys.reserve(2*n);
62     for(int i=0;i<n;++i){
63         long long x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
64         if (x1 > x2) swap(x1, x2);
65         if (y1 > y2) swap(y1, y2);
66         edges.push_back({x1, y1, y2, +1});
67         edges.push_back({x2, y1, y2, -1});
68         ys.push_back(y1); ys.push_back(y2);
69     }
70     sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
71     // Need ys as coordinates for elementary segments; ensure at least 2 distinct values
72     if (ys.size() < 2) { cout << 0 << "\n"; return 0; }
73 
74     sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){
75         if (a.x != b.x) return a.x < b.x;
76         return a.type > b.type; // add before remove at same x
77     });
78 
79     SegTree st(ys);
80     long long area = 0;
81     for(size_t i=0;i<edges.size();){
82         long long x = edges[i].x;
83         // Process all edges at x
84         while (i < edges.size() && edges[i].x == x) {
85             st.add_interval(edges[i].y1, edges[i].y2, edges[i].type);
86             ++i;
87         }
88         if (i < edges.size()){
89             long long dx = edges[i].x - x;
90             area += dx * st.covered_length();
91         }
92     }
93     cout << area << "\n";
94     return 0;
95 }
96

We sweep along x. Each rectangle contributes a +1 update on [y1, y2) at its left edge and a -1 update at its right edge. A segment tree over compressed y maintains the total covered y-length. The area added between consecutive x-events is the covered length multiplied by the horizontal distance to the next event.

Time: O(n log n)Space: O(n)

Closest Pair of Points via Sweep (O(n log n))

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Standard sweep for closest pair of points.
5 // Sort by x; maintain a y-ordered set of points within current best distance in x.
6 // For each new point, remove points whose x is farther than best, then check neighbors in y-window.
7 
8 struct Point { long long x, y; int id; };
9 
10 int main(){
11     ios::sync_with_stdio(false);
12     cin.tie(nullptr);
13 
14     int n; if(!(cin >> n)) return 0;
15     vector<Point> pts(n);
16     for(int i=0;i<n;++i){ cin >> pts[i].x >> pts[i].y; pts[i].id = i; }
17     sort(pts.begin(), pts.end(), [](const Point& a, const Point& b){
18         if (a.x != b.x) return a.x < b.x; return a.y < b.y;
19     });
20 
21     const long double INF = 1e30L;
22     long double best = INF; pair<int,int> ans = {-1,-1};
23 
24     // set of (y, x, id) for ordering by y, tie-break by x
25     set<tuple<long long,long long,int>> box; 
26     int left = 0; // left boundary of sliding window in x
27 
28     for (int i = 0; i < n; ++i) {
29         auto [x, y, id] = pts[i];
30         // Shrink window: remove points with x < x_i - best
31         while (left < i) {
32             long double dx = (long double)pts[i].x - (long double)pts[left].x;
33             if (dx * dx <= best * best) break;
34             box.erase({pts[left].y, pts[left].x, pts[left].id});
35             ++left;
36         }
37         // Find candidates with y in [y - best, y + best]
38         long long ylow = (long long)floor(y - ceil((double)best) - 1);
39         long long yhigh = (long long)ceil(y + ceil((double)best) + 1);
40         auto itlow = box.lower_bound({ylow, LLONG_MIN, INT_MIN});
41         auto ithigh = box.upper_bound({yhigh, LLONG_MAX, INT_MAX});
42         for (auto it = itlow; it != ithigh; ++it) {
43             auto [yy, xx, iid] = *it;
44             long double dx = (long double)x - (long double)xx;
45             long double dy = (long double)y - (long double)yy;
46             long double d2 = dx*dx + dy*dy;
47             if (d2 < best*best) {
48                 best = sqrt(max((long double)0.0, d2));
49                 ans = {id, iid};
50             }
51         }
52         box.insert({y, x, id});
53     }
54 
55     // Output minimal distance and any pair achieving it
56     cout.setf(std::ios::fixed); cout << setprecision(6);
57     if (ans.first == -1) { cout << 0.0 << "\n"; }
58     else cout << (double)best << "\n";
59     return 0;
60 }
61

Sort points by x. Maintain a set ordered by y containing only points whose x is within the current best distance of the current point. Candidates must also lie within a vertical y-window of height 2·best. Checking only these candidates yields an O(n log n) algorithm since each point is inserted and removed once and constant many candidates are typically inspected.

Time: O(n log n)Space: O(n)

Count Intersections Between Axis-Aligned Segments (Fenwick + Sweep)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Given a set of axis-aligned segments, count the number of intersections
5 // between horizontal and vertical segments. Segments are closed.
6 // Input format:
7 // n
8 // For each segment: x1 y1 x2 y2
9 // Exactly those with x1==x2 are vertical; those with y1==y2 are horizontal.
10 
11 struct BIT {
12     int n; vector<long long> f;
13     BIT(int n=0): n(n), f(n+1,0){}
14     void add(int i, long long v){ for(++i;i<=n;i+=i&-i) f[i]+=v; }
15     long long sumPrefix(int i){ long long s=0; for(++i;i>0;i-=i&-i) s+=f[i]; return s; }
16     long long rangeSum(int l, int r){ if(r<l) return 0; return sumPrefix(r) - (l?sumPrefix(l-1):0); }
17 };
18 
19 struct Event{ long long x; int type; long long y1, y2; // type: 0=ADD horizontal y=y1, 1=QUERY vertical [y1,y2], 2=REMOVE horizontal y=y1
20 };
21 
22 int main(){
23     ios::sync_with_stdio(false);
24     cin.tie(nullptr);
25 
26     int n; if(!(cin>>n)) return 0;
27     vector<array<long long,4>> segs(n);
28     for(int i=0;i<n;++i) cin>>segs[i][0]>>segs[i][1]>>segs[i][2]>>segs[i][3];
29 
30     vector<long long> ys; ys.reserve(2*n);
31     vector<Event> ev; ev.reserve(2*n);
32 
33     for(auto&s:segs){
34         long long x1=s[0], y1=s[1], x2=s[2], y2=s[3];
35         if (x1==x2) {
36             // vertical at x=x1, spanning [min(y1,y2), max(y1,y2)]
37             if (y2<y1) swap(y1,y2);
38             ev.push_back({x1, 1, y1, y2});
39             ys.push_back(y1); ys.push_back(y2);
40         } else if (y1==y2) {
41             // horizontal at y=y1, spanning [min(x1,x2), max(x1,x2)]
42             if (x2<x1) swap(x1,x2);
43             ev.push_back({x1, 0, y1, y1}); // add at left x
44             ev.push_back({x2, 2, y1, y1}); // remove at right x
45             ys.push_back(y1);
46         } else {
47             // ignore or handle error: not axis-aligned
48         }
49     }
50 
51     // compress y
52     sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
53     auto getY = [&](long long y){ return int(lower_bound(ys.begin(), ys.end(), y) - ys.begin()); };
54 
55     // Sort events by x; tie-break: ADD before QUERY before REMOVE to count endpoints correctly.
56     sort(ev.begin(), ev.end(), [&](const Event&a, const Event&b){
57         if (a.x!=b.x) return a.x<b.x;
58         return a.type<b.type; // 0<1<2
59     });
60 
61     BIT bit((int)ys.size()+2);
62     long long ans = 0;
63 
64     for(auto &e: ev){
65         if (e.type==0){
66             bit.add(getY(e.y1), +1);
67         } else if (e.type==2){
68             bit.add(getY(e.y1), -1);
69         } else {
70             int ly = getY(e.y1); int ry = getY(e.y2);
71             ans += bit.rangeSum(ly, ry);
72         }
73     }
74 
75     cout << ans << "\n";
76     return 0;
77 }
78

We sweep by x. When we encounter the left endpoint of a horizontal segment, we activate its y by adding +1 in a BIT; at its right endpoint we remove it. For a vertical segment at x, we query how many active horizontals cross its y-range [y1, y2]. Sorting with the tie-break ADD < QUERY < REMOVE ensures shared endpoints are counted according to closed-segment semantics.

Time: O(n log n)Space: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// This program reads n intervals [l, r) and computes the maximum number
5	// of overlapping intervals and one position where this maximum occurs.
6	// We use a classic 1D sweep: +1 at start, -1 at end, sorted by coordinate.
7
8	int main() {
9	ios::sync_with_stdio(false);
10	cin.tie(nullptr);
11
12	int n;
13	if (!(cin >> n)) return 0;
14	vector<pair<long long,int>> events; // (x, delta)
15	events.reserve(2*n);
16	for (int i = 0; i < n; ++i) {
17	long long l, r; cin >> l >> r;
18	// We'll treat intervals as [l, r): start adds, end removes.
19	events.push_back({l, +1});
20	events.push_back({r, -1});
21	}
22	// Tie-breaking: at the same x, process +1 before -1 to treat [l, r) correctly
23	sort(events.begin(), events.end(), [](auto &a, auto &b){
24	if (a.first != b.first) return a.first < b.first;
25	return a.second > b.second; // +1 before -1
26	});
27
28	long long curr = 0, best = 0;
29	long long best_pos = events.empty() ? 0 : events[0].first;
30
31	for (size_t i = 0; i < events.size(); ) {
32	long long x = events[i].first;
33	// apply all deltas at this x
34	while (i < events.size() && events[i].first == x) {
35	curr += events[i].second;
36	++i;
37	}
38	if (curr > best) {
39	best = curr;
40	best_pos = x; // any point in [x, next_x) achieves 'best'
41	}
42	}
43
44	cout << best << " " << best_pos << "\n";
45	return 0;
46	}
47

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute the area of union of axis-aligned rectangles.
5	// Input: n, then n lines: x1 y1 x2 y2 with x1 < x2, y1 < y2 (64-bit ints allowed).
6	// Approach: vertical sweep over rectangle edges; maintain covered y-length using a segment tree
7	// built over compressed y-coordinates. Each edge performs a range add (+1 for left edge, -1 for right).
8
9	struct Node {
10	int cover = 0; // how many intervals cover this segment
11	long long covered = 0; // covered length in this segment (using original y-units)
12	};
13
14	struct SegTree {
15	int n; // number of elementary intervals (m-1 if m distinct y's)
16	vector<Node> st;
17	vector<long long> ys; // coordinates (size m)
18	SegTree(const vector<long long>& coords) {
19	ys = coords;
20	n = (int)ys.size() - 1; // n elementary segments
21	st.assign(4*n+4, {});
22	}
23	void pull(int p, int l, int r) {
24	if (st[p].cover > 0) {
25	st[p].covered = ys[r+1] - ys[l]; // fully covered
26	} else if (l == r) {
27	st[p].covered = 0;
28	} else {
29	st[p].covered = st[p<<1].covered + st[p<<1\|1].covered;
30	}
31	}
32	void update(int p, int l, int r, int ql, int qr, int delta) {
33	if (ql > r \|\| qr < l) return;
34	if (ql <= l && r <= qr) {
35	st[p].cover += delta;
36	pull(p, l, r);
37	return;
38	}
39	int m = (l + r) >> 1;
40	update(p<<1, l, m, ql, qr, delta);
41	update(p<<1\|1, m+1, r, ql, qr, delta);
42	pull(p, l, r);
43	}
44	// External call with [y1, y2) in original coords
45	void add_interval(long long y1, long long y2, int delta) {
46	int l = int(lower_bound(ys.begin(), ys.end(), y1) - ys.begin());
47	int r = int(lower_bound(ys.begin(), ys.end(), y2) - ys.begin()) - 1; // inclusive index of elementary segments
48	if (l <= r) update(1, 0, n-1, l, r, delta);
49	}
50	long long covered_length() const { return st[1].covered; }
51	};
52
53	struct Edge { long long x, y1, y2; int type; }; // type: +1 add, -1 remove
54
55	int main(){
56	ios::sync_with_stdio(false);
57	cin.tie(nullptr);
58
59	int n; if(!(cin >> n)) return 0;
60	vector<Edge> edges; edges.reserve(2*n);
61	vector<long long> ys; ys.reserve(2*n);
62	for(int i=0;i<n;++i){
63	long long x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
64	if (x1 > x2) swap(x1, x2);
65	if (y1 > y2) swap(y1, y2);
66	edges.push_back({x1, y1, y2, +1});
67	edges.push_back({x2, y1, y2, -1});
68	ys.push_back(y1); ys.push_back(y2);
69	}
70	sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
71	// Need ys as coordinates for elementary segments; ensure at least 2 distinct values
72	if (ys.size() < 2) { cout << 0 << "\n"; return 0; }
73
74	sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){
75	if (a.x != b.x) return a.x < b.x;
76	return a.type > b.type; // add before remove at same x
77	});
78
79	SegTree st(ys);
80	long long area = 0;
81	for(size_t i=0;i<edges.size();){
82	long long x = edges[i].x;
83	// Process all edges at x
84	while (i < edges.size() && edges[i].x == x) {
85	st.add_interval(edges[i].y1, edges[i].y2, edges[i].type);
86	++i;
87	}
88	if (i < edges.size()){
89	long long dx = edges[i].x - x;
90	area += dx * st.covered_length();
91	}
92	}
93	cout << area << "\n";
94	return 0;
95	}
96

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Standard sweep for closest pair of points.
5	// Sort by x; maintain a y-ordered set of points within current best distance in x.
6	// For each new point, remove points whose x is farther than best, then check neighbors in y-window.
7
8	struct Point { long long x, y; int id; };
9
10	int main(){
11	ios::sync_with_stdio(false);
12	cin.tie(nullptr);
13
14	int n; if(!(cin >> n)) return 0;
15	vector<Point> pts(n);
16	for(int i=0;i<n;++i){ cin >> pts[i].x >> pts[i].y; pts[i].id = i; }
17	sort(pts.begin(), pts.end(), [](const Point& a, const Point& b){
18	if (a.x != b.x) return a.x < b.x; return a.y < b.y;
19	});
20
21	const long double INF = 1e30L;
22	long double best = INF; pair<int,int> ans = {-1,-1};
23
24	// set of (y, x, id) for ordering by y, tie-break by x
25	set<tuple<long long,long long,int>> box;
26	int left = 0; // left boundary of sliding window in x
27
28	for (int i = 0; i < n; ++i) {
29	auto [x, y, id] = pts[i];
30	// Shrink window: remove points with x < x_i - best
31	while (left < i) {
32	long double dx = (long double)pts[i].x - (long double)pts[left].x;
33	if (dx * dx <= best * best) break;
34	box.erase({pts[left].y, pts[left].x, pts[left].id});
35	++left;
36	}
37	// Find candidates with y in [y - best, y + best]
38	long long ylow = (long long)floor(y - ceil((double)best) - 1);
39	long long yhigh = (long long)ceil(y + ceil((double)best) + 1);
40	auto itlow = box.lower_bound({ylow, LLONG_MIN, INT_MIN});
41	auto ithigh = box.upper_bound({yhigh, LLONG_MAX, INT_MAX});
42	for (auto it = itlow; it != ithigh; ++it) {
43	auto [yy, xx, iid] = *it;
44	long double dx = (long double)x - (long double)xx;
45	long double dy = (long double)y - (long double)yy;
46	long double d2 = dxdx + dydy;
47	if (d2 < best*best) {
48	best = sqrt(max((long double)0.0, d2));
49	ans = {id, iid};
50	}
51	}
52	box.insert({y, x, id});
53	}
54
55	// Output minimal distance and any pair achieving it
56	cout.setf(std::ios::fixed); cout << setprecision(6);
57	if (ans.first == -1) { cout << 0.0 << "\n"; }
58	else cout << (double)best << "\n";
59	return 0;
60	}
61

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Given a set of axis-aligned segments, count the number of intersections
5	// between horizontal and vertical segments. Segments are closed.
6	// Input format:
7	// n
8	// For each segment: x1 y1 x2 y2
9	// Exactly those with x1==x2 are vertical; those with y1==y2 are horizontal.
10
11	struct BIT {
12	int n; vector<long long> f;
13	BIT(int n=0): n(n), f(n+1,0){}
14	void add(int i, long long v){ for(++i;i<=n;i+=i&-i) f[i]+=v; }
15	long long sumPrefix(int i){ long long s=0; for(++i;i>0;i-=i&-i) s+=f[i]; return s; }
16	long long rangeSum(int l, int r){ if(r<l) return 0; return sumPrefix(r) - (l?sumPrefix(l-1):0); }
17	};
18
19	struct Event{ long long x; int type; long long y1, y2; // type: 0=ADD horizontal y=y1, 1=QUERY vertical [y1,y2], 2=REMOVE horizontal y=y1
20	};
21
22	int main(){
23	ios::sync_with_stdio(false);
24	cin.tie(nullptr);
25
26	int n; if(!(cin>>n)) return 0;
27	vector<array<long long,4>> segs(n);
28	for(int i=0;i<n;++i) cin>>segs[i][0]>>segs[i][1]>>segs[i][2]>>segs[i][3];
29
30	vector<long long> ys; ys.reserve(2*n);
31	vector<Event> ev; ev.reserve(2*n);
32
33	for(auto&s:segs){
34	long long x1=s[0], y1=s[1], x2=s[2], y2=s[3];
35	if (x1==x2) {
36	// vertical at x=x1, spanning [min(y1,y2), max(y1,y2)]
37	if (y2<y1) swap(y1,y2);
38	ev.push_back({x1, 1, y1, y2});
39	ys.push_back(y1); ys.push_back(y2);
40	} else if (y1==y2) {
41	// horizontal at y=y1, spanning [min(x1,x2), max(x1,x2)]
42	if (x2<x1) swap(x1,x2);
43	ev.push_back({x1, 0, y1, y1}); // add at left x
44	ev.push_back({x2, 2, y1, y1}); // remove at right x
45	ys.push_back(y1);
46	} else {
47	// ignore or handle error: not axis-aligned
48	}
49	}
50
51	// compress y
52	sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
53	auto getY = [&](long long y){ return int(lower_bound(ys.begin(), ys.end(), y) - ys.begin()); };
54
55	// Sort events by x; tie-break: ADD before QUERY before REMOVE to count endpoints correctly.
56	sort(ev.begin(), ev.end(), [&](const Event&a, const Event&b){
57	if (a.x!=b.x) return a.x<b.x;
58	return a.type<b.type; // 0<1<2
59	});
60
61	BIT bit((int)ys.size()+2);
62	long long ans = 0;
63
64	for(auto &e: ev){
65	if (e.type==0){
66	bit.add(getY(e.y1), +1);
67	} else if (e.type==2){
68	bit.add(getY(e.y1), -1);
69	} else {
70	int ly = getY(e.y1); int ry = getY(e.y2);
71	ans += bit.rangeSum(ly, ry);
72	}
73	}
74
75	cout << ans << "\n";
76	return 0;
77	}
78