How to make sure that a given set of points lie on the boundary of a possible square? Given a set of integral coordinates , check whether all the points given lie on side of a possible square such that axis of the square so formed lie parallel to both X-axis and Y-axis .
Suppose points are (0,0) , (1,1) , (2,2) .
Answer is not possible .
Suppose points are (0 , 0) , (0,2) , (0,5) , (0,7) , (3,0)
Answer is square is possible and minimum length of the side is 7 .
I tried it and came up with many corner cases and it seemed impossible to tackle them individually . I was wondering if anyone can give a more generalised approach towards this kind of problem and how to think in the right direction .
Thanks in advance .
 A: Let $\displaystyle x_1 = \min_{(x,y) \in P}{x}$, $\displaystyle x_2 = \max_{(x,y) \in P}{x}$, $\displaystyle y_1 = \min_{(x,y) \in P}{y}$ and $\displaystyle y_2 = \min_{(x,y) \in P}{y}$, where $P$ is the set of points (which I'm assuming to be finite). Consider the (possibly degenerate) rectangle $R$ given by the lines $y = x_1$, $y = x_2$, $x = y_1$ and $x = y_2$.
Now we consider the following two cases:


*

*$x_1 = x_2$ or $y_1 = y_2$: that is, all points lie on a line. There are infinite squares satisfying the conditions; choose any segment passing through them and form a square from this segment. If you want the side to be minimal, in the case $x_1 = x_2$, choose its endpoints to be $(x_1, \bar y)$ and $(x_2, \bar y)$, where $\bar y$ is the common $y$ coordinate of all points. The case $y_1 = y_2$ is analogous.

*$x_1 \neq x_2$ and $y_1 \neq y_2$: in this case, for a square to exist, these two conditions must hold:


*

*$R$ needs to be a square, that is $x_2 - x_1 = y_2 - y_1$ (= square length).

*each point $(x, y)$ has to satisfy the condition $$x = x_1 \lor x = x_2 \lor y = y_1 \lor y = y_2$$


A: Let $X=\{(x_i,y_i)\,\mid\,1\le i\le n\}$ be a collection of $n$ points in the plane. If the points lie on a square with sides parallel to the $x$-axis and $y$-axis, then either the $x_i$'s take on at most 2 distinct values in $X$ and/or the $y_i$'s take on at most 2 distinct values in $X$. 
If both the $x_i$'s and $y_i$'s take on more than two distinct values in $X$, then there can be no one square on which all the points lie.
However this is only a necessary condition. These points could lie on a rectangle. In order to avoid this, suppose the $x$ coordinate is the one that takes on at most 2 distinct values. We must have
$$
\max_{1\le i\le n}(y_i)-\min_{1\le i\le n}(y_i)=x_2-x_1
$$
otherwise the points will lie on a rectangle!
