Covered by images
A satellite photographs the Earth in frames. On a map in a projection where distances are measured in metres, each frame is a rectangle with sides along the axes. Adjacent frames of one orbit overlap, orbits cross each other, and the same place is photographed many times. What area of the map is covered by at least one frame?
Input
The first line holds n (1 ≤ n ≤ 50,000), the number of frames. Then n lines: x1 y1 x2 y2, the lower left and upper right corners of a frame, integers, 0 ≤ x1 < x2 ≤ 109, 0 ≤ y1 < y2 ≤ 109. Frames may coincide.
Output
The area of the union of the frames, a single integer.
Examples
Example 1
3 0 0 4 3 2 1 6 5 5 0 7 2
27
Example 2
3 0 0 10 10 2 2 4 4 0 0 10 10
100
Limits
- Time · Python
- 13500 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Draw a vertical line and move it from left to right. Between two neighbouring left or right edges of frames the length of the covered part of the line does not change: the area of this strip is that length times the width of the strip.
2Hint 2
What remains is to know the covered length quickly after each event: a segment [y1, y2] is added to the line or removed from it. Recomputing it from scratch over all strips is O(n) per event and O(n²) in all.
3The idea
A sweep line and a segment tree over compressed y coordinates. A node stores how many segments cover it entirely (cnt) and the covered length within it (cov): if cnt > 0, that is the whole length of the node, otherwise the sum of the children. Adding and removing a segment touch O(log n) nodes, and the answer to “how much is covered” lies at the root.
4Walkthrough
Sort the distinct y values, giving at most 2n − 1 elementary strips. Each frame gives two events: (x1, +1) and (x2, −1). Events go in increasing order of x; before an event is processed, cov[root] · (x − xprev) is added to the answer. Lazy operations are not needed: a segment added to nodes is removed from exactly the same nodes, since the decomposition of [a, b) into tree nodes is unique, so cnt never becomes negative and never descends to the children. This is proved in the article’s section on the area of a union.
4+Solution
5Complexity
O(n log n): sorting and 2n tree updates at O(log n) each. The answer reaches 1018; in Go and C a 64-bit type is needed, and it fits.
6Common mistakes
- Recomputing the covered length in full. This is
wrong.py: on a thousand frames it is in time, on fifty thousand it is not. - The sum of areas minus pairwise intersections. If a place was photographed three times, too much is subtracted: the inclusion–exclusion formula needs all intersections, and there are exponentially many.
- A maximum instead of a count. A node needs a counter, not a “covered” flag: when one of two frames covering a node ends, the node stays covered.
- Points instead of strips. A tree leaf is the gap between neighbouring distinct y values, not the coordinate itself; otherwise the length between them is lost.
Algorithms behind it
O((n + k) log n)
3 problems
DS
Data structure
Segment tree
The minimum, maximum and sum on any range with updates on the fly: both in O(log n).
O(log n) per query and per update
2 problems
TEC
Technique
Coordinate compression
Replace values up to a billion by their ranks in order, and build arrays and trees over the ranks.
O(n log n) to compress
2 problems