The prolem deals with horizontal or vertical rectangles on the plane. A rectangle is specified by giving its minimum and maximum x- and y-coordinates x1, x2, y1, and y2. E.g., 0 5 2 3 is a rectangle whose width is five units, height is one unit, and left bottom corner is at the coordinates (0,2). A rectangle consists of the points (x,y) that satisfy x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2. Two rectangles intersect each other, if they have at least one point in common.
The task is to write a program that runs in O(n log n) time, reads n rectangles and tells whether they contain any two that intersect each other. If the same rectangle is given twice in the input, then it is interpreted as two rectangles. Therefore, if the input is 0 1 0 1 and 3 4 3 4, then the answer is "no", but if the input is 0 1 0 1, 3 4 3 4 and 0 1 0 1, then the answer is "yes", because the first and last 0 1 0 1 intersect each other.
Without the requirement of the O(n log n) running time, the program could test each rectangle against each other. However, the running time of this very simple algorithm is Θ(n2), so such a program will not be accepted as a solution. However, you may implement this simple algorithm and use it as a testing aid, by comparing its answers to the answers provided by your real solution.
It is not easy to invent a fast enough algorithm. It is easy to invent tricks that improve the running time, but it is difficult to ensure that they guarantee the required running time in all cases.
The problem is Exercise 15.3-7 of the textbook Cormen, Leiserson, Rivest 1990: Introduction to Algorithms. In the newer version with Stein as a fourth author it is Exercise 14.3-7. Reading the corresponding chapter of the book thus helps solving the problem. It is also possible to get a little help from the teacher, but only after reading the chapter. Solutions that differ from the book are allowed, but then the document must contain a detailed and clear correctness and performance proof. Therefore, presenting such a solution requires almost researcher-level skills.
This project is thus mostly a programming project, where the basic ideas are in the book, and they only need to be converted into a running program. However, a lot of care is needed to get the program work correctly.
It is possible that bigger inputs than are used in the tests are needed to demonstrate the superiority of the O(n log n) algorithm over the simple Θ(n2) algorithm, in particular if the implementation of the former is clumsy. For this reason, with this topic it is not necessary to meet the requirement in the general instructions saying that the solution must be faster in tests than simple solutions. It is best to think of this topic as an exercise that improves programming skills, and not as the writing of a program that is useful in practise.
The input consists of natural numbers. It consists of the following parts:
<The input> ::= <number of rectangles> <Rectangle>* <Rectangle> ::= <x1> <x2> <y1> <y2>
The first rectangle given in the input is called rectangle 1, the second one is rectangle 2, and so on.
If no two rectangles intersect each other, then the proram must output zero (0). In the opposite case the program must output such natural numbers i and j that i < j and rectangles i and j intersect each other. If there are more than one pairs of rectangles that intersect each other, then it does not matter which pair the program prints.