In this HackerEarth Earth and The Meteorites problem solution Once upon a time, the Earth was a flat rectangular landmass. And there was no life. It was then that the sky lit up with meteorites falling from out of space. Wherever they fell on the planet, a river was born, which flowed in all 4 directions (North, East, West, South), till the waters reached the edge of the Earth and simply fell off into space.

Now, these rivers criss-crossed and divided the one huge landmass (Pangaea) into many smaller landmasses. Now the lifeless (there was no life, remember?), want to know the number of landmasses on the planet after all the meteorites have fallen. They also want to know the area of the smallest and largest landmass. Can you help the lifeless in this question?

HackerEarth Earth and The Meteorites problem solution


HackerEarth Earth and The Meteorites problem solution.

#include<bits/stdc++.h>
using namespace std;

void eval()
{
int n,m,q,x,y;
cin>>n>>m;
cin>>q;
set<int> xAxis;
set<int> yAxis;
xAxis.insert(1);
yAxis.insert(1);
xAxis.insert(n);
yAxis.insert(m);

for(int i=0;i<q;i++)
{
cin>>x>>y;
xAxis.insert(x);
yAxis.insert(y);
}
long long cuts = (xAxis.size()-1)*1LL*(yAxis.size()-1);
cout<<cuts<<" ";

int xMax = 0, xMin = n;
int yMax = 0, yMin = m;
set<int>::iterator it=xAxis.begin();
set<int>::iterator it2=it;
it2++;
for(;it2!=xAxis.end();it++,it2++)
{
xMax=max(xMax, *it2-*it);
xMin=min(xMin, *it2-*it);

}
it=yAxis.begin();
it2=it;
it2++;
for(;it2!=yAxis.end();it++,it2++)
{
yMax=max(yMax, *it2-*it);
yMin=min(yMin, *it2-*it);
}
cout<<xMin*1LL*yMin<<" "<<xMax*1LL*yMax<<endl;

}

int main()
{
int t;
cin>>t;
while(t--)
{
eval();
}
}

Second solution

#include<bits/stdc++.h>

using namespace std;

int tests, n, m, q;
vector<int> xs, ys;
int cntx, cnty;
int bx, by, cx, cy;
int sq;

int main(){
ios_base::sync_with_stdio(0);

cin >> tests;

for (; tests; --tests)
{
cin >> n >> m >> q;

sq += q;

xs.clear();
ys.clear();
xs.push_back(1);
xs.push_back(n);
ys.push_back(1);
ys.push_back(m);

for (; q; --q)
{
int a, b;
cin >> a >> b;

xs.push_back(a);
ys.push_back(b);
}

sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());

cntx = cnty = 0;
bx = by = max(n, m);
cx = cy = 0;

for (int i = 0; i < xs.size(); i++)
{
if (i>0 && xs[i] != xs[i - 1])
{
cntx++;
bx = min(bx, xs[i] - xs[i - 1]);
cx = max(cx, xs[i] - xs[i - 1]);
}
}

for (int i = 0; i < ys.size(); i++)
{
if (i>0 && ys[i] != ys[i - 1])
{
cnty++;
by = min(by, ys[i] - ys[i - 1]);
cy = max(cy, ys[i] - ys[i - 1]);
}
}

cout << 1ll * cntx*cnty << " " << 1ll * bx*by << " " << 1ll * cx*cy << endl;
}

return 0;
}