In this HackerEarth Largest Square problem solution, You are given N points on the infinite 2 - D plane. You need to find 4 such points among these N points, such that, they form a square with positive side length and whose sides are parallel to the x and y-axis.

If there are multiple choices of 4 such points, choose those which form the square of the largest side. If there are still multiple choices of 4 such points, choose those 4 points in which the bottom left point has a lower y co-ordinate. If there are still multiple choices of 4 such points, choose those 4 points in which the bottom left point has a lower x coordinate.


HackerEarth Largest Square problem solution


HackerEarth Largest Square problem solution.

#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
assert(n >= 1 and n <= 2000);
map<pair<int, int> , bool> is;
map<int, vector<int> > v;
for(int i = 1; i <= n; i++) {
int x, y;
scanf("%d%d", &x, &y);
assert(x >= 1 and x <= 1000000000 and y >= 1 and y <= 1000000000);
is[make_pair(x, y)] = true;
v[y].push_back(x);
}
for(auto &it : v) {
sort(it.second.begin(), it.second.end());
}
int mx = -1, ansX, ansY;
for(auto it : v) {
for(int j = 0; j < (int)it.second.size(); j++) {
int x1 = it.second[j], y = it.first;
for(int k = j + 1; k < (int)it.second.size(); k++) {
int x2 = it.second[k];
int dif = x2 - x1;
if(dif == 0 or dif <= mx) continue;
if(is.find(make_pair(x1, y + dif)) == is.end()) continue;
if(is.find(make_pair(x2, y + dif)) == is.end()) continue;
ansX = x1, ansY = y;
mx = dif;
}
}
}
if(mx == -1) cout << mx << endl;
else cout << ansX << " " << ansY << endl;
return 0;
}