Total and Distinct Rectangle Boundaries
Национална олимпиада - Областен кръг 2026
Submission name: rect.cpp
Problem summary
Given axis-aligned rectangles, print the sum of their perimeters and the total length covered by their boundary segments. Coincident boundary portions count once in the second answer. This is not the perimeter of the union of filled rectangles.
Input
n followed by x1 y1 x2 y2 for every rectangle.
Output
Total perimeter, then distinct boundary length, on separate lines.
Constraints
1 ≤ n ≤ 20000; integer coordinates 0 ≤ x1 < x2 ≤ 1000 and 0 ≤ y1 < y2 ≤ 1000; source memory limit 3 MB.
Worked example
The worked example illustrates the rule described in the analysis.
Input
2 0 0 1 2 1 0 2 1
Output
10 9
Solution analysis
- Add 2(width+height) per rectangle to the total. Store its two horizontal sides as intervals labelled by y and its two vertical sides as intervals labelled by x.
- Process orientations separately. Sort intervals by their fixed coordinate, then left endpoint, then right endpoint. Merge overlapping or touching intervals on the same supporting line.
- Add the length of each merged interval. Horizontal and vertical segments intersect only in points, which have length zero; their two totals can therefore be added directly.
- The sample has perimeter sum 6+4=10. The rectangles share one unit side, so distinct boundary length is 9. Even a boundary lying inside another filled rectangle remains part of the boundary-segment union.
Why it works
Sorting places intervals on each supporting line in order. The running merged interval covers exactly the current connected union component; flushing it counts every covered portion once. Different supporting lines share no positive-length segment, and perpendicular intersections have zero length.
Watch out. Do not confuse union of boundaries with boundary of the union. Merge only collinear segments. Touching endpoints add no extra length. Identical rectangles double the first answer, not the second.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Sorting places intervals on each supporting line in order. The running merged interval
// covers exactly the current connected union component; flushing it counts every covered portion once.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
struct Segment{
int coordinate,left,right;
};
long long unionLength(vector<Segment>&segments){
sort(segments.begin(),segments.end(),[](const Segment&a,const Segment&b){
if(a.coordinate!=b.coordinate){
return a.coordinate<b.coordinate;
}
if(a.left!=b.left){
return a.left<b.left;
}
return a.right<b.right;
});
long long length=0;
int coordinate=-1,left=0,right=0;
for(const Segment&segment:segments){
if(segment.coordinate!=coordinate||segment.left>right){
length+=right-left;
coordinate=segment.coordinate;
left=segment.left;
right=segment.right;
}
else{
right=max(right,segment.right);
}
}
return length+right-left;
}
int main(){
int n;
cin>>n;
vector<Segment>horizontal,vertical;
horizontal.reserve(2*n);
vertical.reserve(2*n);
long long total=0;
for(int i=0;i<n;++i){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
total+=2LL*(x2-x1+y2-y1);
horizontal.push_back({y1,x1,x2});
horizontal.push_back({y2,x1,x2});
vertical.push_back({x1,y1,y2});
vertical.push_back({x2,y1,y2});
}
cout<<total<<'\n';
cout<<unionLength(horizontal)+unionLength(vertical)<<'\n';
}