You are given n points in the plane (each given by a pair (x, y) of coordinates). Your job is to find the pair of points that are closest to each other, the same problem we aimed to solve in Lecture 7. During that lecture, we discussed a deterministic algorithm for this with worst-case running time theta(n log n). Now, you are asked to design an algorithm runs in O(n) expected time for uniformly distributed inputs; that is, assuming that the inputs' coordinates (x_1, y_1, x_2, y_2, . ... ., x_n, y_n) are selected independently, uniformly and independently in [0, 1]. The algorithm can be deterministic. It should run in expected time O(n) where the expectation is taken over the choice of the input. The output should be the coordinates of the two closest points among those in the input. First, explain your algorithm concisely in English (feel free to use pictures). Second, specify your algorithm using clear pseudocode. Prove that your algorithm is correct. Your algorithm has to find the nearest pair of inputs on all possible inputs-you are not allowed to use the fact that the points are randomly distributed for correctness. Prove that your algorithm's expected running time is O(n). (We assume here that figuring out which cell a point belongs to can be done in constant time (say, by dividing each of the coordinates by 1/t and rounding down to the nearest integer), and that the operations needed to compute distance can also be done in constant time.)