Largest Square
Practice
4 (49 votes)
Arrays
Data structures
Easy
Multi Dimensional
Problem
86% Success 5346 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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 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 co-ordinate.

Input:

First line contains a single integer $$N$$, denoting the number of points on the $$2-D$$ plane. Each of the next $$N$$ lines contain $$2$$ space separated integers $$X$$ and $$Y$$, these denote the x and y co-ordinates of the point.

Output:

Print $$2$$ space separated integers, the co-ordinates of the bottom left point of the square found. If there are no squares present, print $$-1$$.

Constraints:

$$1 \le N \le 2000$$

$$1 \le X, Y \le 10^9$$

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
28 votes
Tags:
Ad-HocApprovedData StructuresEasy
Points:30
20 votes
Tags:
ApprovedEasy
Points:30
21 votes
Tags:
ArraysData StructuresMulti-dimensional