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.

`#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;

}

## 0 Comments