Connected Regions of Grounded Rectangles
National Olympiad — National round (2017 season)
Submission name: rect.cpp
Problem summary
Axis-aligned rectangles each have one horizontal side on the x-axis, lying above or below it. Intersections or side contacts connect regions; a point contact alone does not. Find the number of connected regions, total union area, and largest region area.
Source clarification. This 2017 National-round task was shared by Groups C and D; its existing permanent URL is retained.
Input
N followed by opposite corners x1 y1 x2 y2 of each nondegenerate rectangle, in either order.
Output
Three lines: region count, total area, largest region area.
Constraints
1 ≤ N ≤ 100000; 0 ≤ x1,x2 ≤ 10^9; −10000 ≤ y1,y2 ≤ 10000. Coordinates are integers.
Worked example
Input and output for the worked example discussed below.
Input
8 1 0 9 2 3 0 7 4 4 0 8 -2 10 0 14 2 14 0 19 -2 16 0 19 -4 17 0 19 -3 21 0 25 -1
Output
4 60 32
Solution analysis
- First process the upper and lower half-planes separately. On the same side, overlapping closed x-intervals connect rectangles, including endpoint equality: their vertical sides share positive height. Sorting by the left endpoint and maintaining the farthest right endpoint partitions each side into connected components.
- Compute each same-side component’s union area by a skyline sweep. Create events at all starts and ends. Between event coordinates, the union height is the maximum active height. A max-heap stores (height,right endpoint); lazily remove expired rectangles whenever they reach its top. Add width times maximum height for each interval.
- Opposite-side components meet only along y=0, and connect only when their x-interval intersection has positive length. With integer coordinates this meets the at-least-one-centimetre requirement. A shared endpoint gives only point contact. The components on each side are ordered and disjoint, allowing a two-pointer sweep over all cross-axis overlaps.
- Use DSU to join components found by the two-pointer sweep. Sum same-side skyline areas into their final roots. Upper and lower interiors are disjoint, so these areas add without double counting.
- In the sample the first two upper rectangles cover 24 units of area; their connected lower rectangle contributes 8, making a region of area 32. The upper [10,14] rectangle has area 8, the next lower group has area 16, and the final rectangle area 4. The middle two only share a point, so there are four regions totaling 60.
Why it works
Same-side connectivity equals closed-interval connectivity because all rectangles share the baseline. The skyline maximum correctly integrates the union area. Opposite-side connectivity is exactly positive interval overlap on the axis; the ordered sweep finds every such overlap. DSU takes the transitive closure of these joins, so aggregating same-side areas by final root gives exactly the connected-region areas.
Watch out. Count union area, not the sum of input rectangle areas. Same-side endpoint equality connects but opposite-side equality does not. Normalize both corner orders. Expired heap entries must be removed before using a newly exposed maximum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<numeric>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
struct Rectangle{
long long left;
long long right;
int height;
};
struct Component{
long long left;
long long right;
long long area;
};
vector<Component>build(vector<Rectangle>rectangles){
sort(rectangles.begin(),rectangles.end(),[](const Rectangle&a,const Rectangle&b){
return a.left<b.left;
});
vector<Component>components;
for(int first=0;first<int(rectangles.size());){
int end=first+1;
long long right=rectangles[first].right;
while(end<int(rectangles.size())&&rectangles[end].left<=right){
right=max(right,rectangles[end].right);
end++;
}
vector<pair<long long,int>>events;
for(int i=first;i<end;i++){
events.push_back({rectangles[i].left,i});
events.push_back({rectangles[i].right,-1});
}
sort(events.begin(),events.end());
priority_queue<pair<int,long long>>active;
long long previous=events.front().first;
long long area=0;
for(auto[x,index]:events){
// Between event positions, the union height is the active maximum.
if(!active.empty()){
area+=(x-previous)*active.top().first;
}
previous=x;
while(!active.empty()&&active.top().second<=x){
active.pop();
}
if(index>=0){
active.push({rectangles[index].height,rectangles[index].right});
}
}
components.push_back({rectangles[first].left,right,area});
first=end;
}
return components;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<Rectangle>above;
vector<Rectangle>below;
for(int i=0;i<n;i++){
long long x1;
long long x2;
int y1;
int y2;
cin>>x1>>y1>>x2>>y2;
Rectangle rectangle{min(x1,x2),max(x1,x2),max(abs(y1),abs(y2))};
if(max(y1,y2)>0){
above.push_back(rectangle);
}
else{
below.push_back(rectangle);
}
}
vector<Component>upper=build(above);
vector<Component>lower=build(below);
int total=upper.size()+lower.size();
vector<int>parent(total);
iota(parent.begin(),parent.end(),0);
auto find=[&](int vertex){
int root=vertex;
while(root!=parent[root]){
root=parent[root];
}
while(vertex!=root){
int next=parent[vertex];
parent[vertex]=root;
vertex=next;
}
return root;
};
int i=0;
int j=0;
while(i<int(upper.size())&&j<int(lower.size())){
// Opposite sides need positive overlap, rather than point contact.
if(max(upper[i].left,lower[j].left)<min(upper[i].right,lower[j].right)){
parent[find(i)]=find(upper.size()+j);
}
if(upper[i].right<lower[j].right){
i++;
}
else{
j++;
}
}
vector<long long>areas(total,0);
for(int index=0;index<int(upper.size());index++){
areas[find(index)]+=upper[index].area;
}
for(int index=0;index<int(lower.size());index++){
areas[find(upper.size()+index)]+=lower[index].area;
}
int count=0;
long long totalArea=0;
long long largest=0;
for(int index=0;index<total;index++){
if(find(index)==index){
count++;
totalArea+=areas[index];
largest=max(largest,areas[index]);
}
}
cout<<count<<'\n'<<totalArea<<'\n'<<largest<<'\n';
return 0;
}