Rectangular Gardens
National Olympiad — National round (2013 season)
Submission name: garden.cpp
Problem summary
Given N distinct points, count positive-area axis-aligned rectangles having an input point at each of their four corners.
Input
N, followed by N coordinate pairs.
Output
The rectangle count.
Constraints
1≤N≤50000; coordinates in [−1000000,1000000]; no duplicate points.
Worked example
An independently prepared example for this explanation.
Input
6 0 0 1 0 1 1 0 1 3 0 3 1
Output
3
Solution analysis
- Group points by x-coordinate and compress all y-coordinates. A rectangle is a pair of columns sharing a pair of distinct y-values. Set a threshold B≈√N and call columns of at most B points small.
- For small columns, generate every pair of y-values and sort the encoded pairs. If a pair occurs in f small columns, it contributes f(f−1)/2 rectangles. There are at most O(NB) generated pairs.
- For each large column, mark its y-values and scan every small column plus only later large columns. If another column shares t y-values, add t(t−1)/2. There are at most N/B large columns. The sample has three columns sharing y=0 and y=1, so choosing any two columns gives one of three rectangles.
Why it works
A positive-area rectangle has two distinct x-values and two distinct shared y-values, uniquely determining its two columns and y-pair. The sorted-pair method counts all small-small column pairs exactly once. The marked-set method counts all pairs with at least one large column, and its ordering avoids counting large-large pairs twice. These cases partition all rectangles.
Watch out. Use a 64-bit answer and pair key. Count combinations of shared y-values, not just one rectangle per column pair. Avoid generating all pairs inside a very large column.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<cstdint>
// Algorithm: Group points by x-coordinate and compress all y-coordinates.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count;
cin>>count;
vector<pair<int,int>>points(count);
vector<int>ys;
for(auto&point:points){
cin>>point.first>>point.second;
ys.push_back(point.second);
}
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
sort(points.begin(),points.end());
vector<vector<int>>columns;
int previousX=0;
for(int i=0;i<count;i++){
if(i==0||points[i].first!=previousX){
columns.emplace_back();
previousX=points[i].first;
}
int y=lower_bound(ys.begin(),ys.end(),points[i].second)-ys.begin();
columns.back().push_back(y);
}
int threshold=max(1,static_cast<int>(sqrt(count)));
uint64_t base=ys.size();
vector<uint64_t>pairs;
for(const auto&column:columns){
if(static_cast<int>(column.size())<=threshold){
for(size_t i=0;i<column.size();i++){
for(size_t j=i+1;j<column.size();j++){
pairs.push_back(static_cast<uint64_t>(column[i])*base+column[j]);
}
}
}
}
sort(pairs.begin(),pairs.end());
long long answer=0;
for(size_t first=0;first<pairs.size();){
size_t last=first+1;
while(last<pairs.size()&&pairs[last]==pairs[first]){
last++;
}
long long frequency=last-first;
answer+=frequency*(frequency-1)/2;
first=last;
}
vector<int>marked(ys.size(),-1);
for(int large=0;large<static_cast<int>(columns.size());large++){
if(static_cast<int>(columns[large].size())<=threshold){
continue;
}
for(int y:columns[large]){
marked[y]=large;
}
for(int other=0;other<static_cast<int>(columns.size());other++){
if(static_cast<int>(columns[other].size())>threshold&&other<=large){
continue;
}
long long shared=0;
for(int y:columns[other]){
if(marked[y]==large){
shared++;
}
}
answer+=shared*(shared-1)/2;
}
}
cout<<answer<<'\n';
}