Consider m rectangles, where the i-th rectangle is represented by the x- and y-coordinates Xil < Xi2 and Yil < Yi2 of its vertices. Here we assume that Yil is negative and Yi2 is positive to simplify the solution, i.e., all rectangles intersect with the x-axis. You are further given a set of n >= m points (a1, b1）,（a2，b2），．．．，（an，bn）， and would like to know whether each point is covered by at least one of the rectangles. Design an algorithm for this problem with a running time faster than O(mn), and analyze its correctness and running time. Hint: First use a divide-and-conquer algorithm to find the area covered by the rectangles, so that for any x-coordinate you can find the maximum and minimum y-coordinates covered by the rectangles. Then, process the points one by one.
Consider m rectangles, where the i-th rectangle is represented by the x- and y-coordinates Xil < Xi2 and Yil < Yi2 of its vertices. Here we assume that Yil is negative and Yi2 is positive to simplify the solution, i.e., all rectangles intersect with the x-axis. You are further given a set of n >= m points (a1, b1）,（a2，b2），．．．，（an，bn）， and would like to know whether each point is covered by at least one of the rectangles. Design an algorithm for this problem with a running time faster than O(mn), and analyze its correctness and running time.
Hint: First use a divide-and-conquer algorithm to find the area covered by the rectangles, so that for any x-coordinate you can find the maximum and minimum y-coordinates covered by the rectangles. Then, process the points one by one.
Step by step
Solved in 3 steps
