# Closest Pair - Question 6 Answers

## 6

Replace lines 20 thru 32 in the pseudo code with the code below to remove the no duplicate x value constraint.

\begin{algorithm}
\caption{Closest Points With Duplicate x Values}
\begin{algorithmic}
\STATE \COMMENT{Notice that we now defining the divide by the entire point, not just the x value}
\STATE divide $\gets Ax_{\text{mid -1}}$
\STATE
\STATE left-y $\gets \emptyset$
\STATE right-y $\gets \emptyset$
\FOR{$i \in Ay$}
\STATE \COMMENT{If x is equal to the divide, split on the y value}
\IF{i.x = divide.x}
\IF{$i.y \leq$ divide.y}
\STATE left-y $\gets \text{left-y} \cup \{i\}$
\ELSE
\STATE right-y $\gets \text{right-y} \cup \{i\}$
\ENDIF
\ELSEIF{$i.x \leq$ divide.x}
\STATE left-y $\gets \text{left-y} \cup \{i\}$
\ELSE
\STATE right-y $\gets \text{right-y} \cup \{i\}$
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}


Additionally, the reference to divide on line 43 must change to divide.x.