Problem 1 k-closest points to the origin We have a list of points on the plane. Find the k closest points to the origin, (0,0). (Here, the distance between two points on a plane is the Euclidean distance.) You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.) Example 1 Input: points = [[1,3), (-2,2]], k = 1 Output: [[-2, 2]] Explanation: The distance between (1,3) and the origin is 10. The distance between (-2,2) and the origin is V8. Since V8 < V10, (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [(-2,2]]. Example 2 Input: points = [[3, 3), (5, -1], [-2, 4]], k = 2 Output: [[3,3), (-2, 4]] (The answer (1-2, 4), (3, 3]] would also be accepted.) It is important that you solve this problem using divide and conquer. That is, you have to reduce the original problem into one or more subproblems, recursively solve the subproblems, and then combine the solutions to obtain the solution to the original problem. Your solution should take O(n) time in the worst case. Note that you cannot use sorting, as this will take O(n log n) time. Note that the LeetCode webpage may accept a solution that is not O(n) in the worst case. By contrast, we require the solution to be O(n) in the worst case. Additionally, some solutions on LeetCode do not use divide and conquer. These are not acceptable solutions. Some solutions posted may also be wrong. In any case, a solution that is largely copied from another source (e.g., verbatim or made to look different by simply changing variable names) will be in violation of the Academic Honesty Policy. The following must be submitted. (a) Writeup (50 Points) • Pseudocode for your solution, with an explanation in words why your solution works. (25 points) • Analysis, showing the correctness of your algorithm and its complexity (i.e., its runtime). (25 points) (b) Source Code (50 Points) • Write your solution in Python, C, C++, Java, or JavaScript. • Your code should be well written and well commented. • A comment with a link to your Leet Code profile (e.g., https://leetcode.com/jane-doe/) and a statement of whether or not your code was accepted by Leet Code. We will verify whether your code is accepted. • We must be able to directly copy and paste your code into LeetCode at the Leet Code problem page. If your code does not compile on Leet Code, it will will receive zero points. Under no circumstances will we attempt to modify any submission, so be sure the code you submit works. 1 Pseudocode and Explanation Algorithm 1 Closest Points - k closest points to the origin 1: def CLOSESTPOINTS(S, k): Input An array S of points in the plane and a positive integer k. Output The k points in S closest to the origin. 2: SI if n= some number: 4: Base Case Stuff else: 6: Recursive Step Stuff n 3: ► Base Case 5: Recursive Step 2 Analysis