closest pair algorithm that runs in O(nlogn) time. However, that algorithm can be improved further when additional assumption is made. Here is one. Suppose that there are n^2 bugs sitting on a piece of paper of size n by n. Any two bugs must stay away by at least 1. Each bug is given as a pair of coordinates. Design a linear-time algorithm that nds the closest pair of bugs. (Hint: since the input size is n^2, the linear time here really means the running time is O(n^2) where the n^2 is the number of bugs.)