Problem 1 (30 points). An axis-aligned rectangle is a rectangle with edges parallel to the coordinate axes. Given n points with their x and y coordinate values, design an O(nlogn) time Divide-and-Conquer algorithm which finds an axis-aligned rectangle with minimum perimeter that covers at least 3 points out of the n given points. In the following example, n 5, a (2,3), b (3,2), c (4,4), d (6,1), and e(7,2). The minimum perimeter axis-aligned rectangle R covers a, b, and c. The vertices of R are (2,2), (2,4), (4,2), and (4,4) 4 4 Problem 1 (30 points). An axis-aligned rectangle is a rectangle with edges parallel to the coordinate axes. Given n points with their x and y coordinate values, design an O(nlogn) time Divide-and-Conquer algorithm which finds an axis-aligned rectangle with minimum perimeter that covers at least 3 points out of the n given points. In the following example, n 5, a (2,3), b (3,2), c (4,4), d (6,1), and e(7,2). The minimum perimeter axis-aligned rectangle R covers a, b, and c. The vertices of R are (2,2), (2,4), (4,2), and (4,4) 4 4