Overlap ------- Your boss at Applied Counting Mechanisms has signed a contract to count the number of pairs of rectangles that overlap each other within very large sets of such rectangles. You have been given the job of writing the program to do this, with an emphasis on optimization due to the large sizes of the sets. Input ----- A sequence of test cases. Each test case begins with a line containing the test case name. This is followed by rectangle description lines each of the form Xmin Xmax Ymin Ymax denoting the rectangle [Xmin,Xmax] x [Ymin,Ymax]. The last line of the test case contains just `*'. All numbers are integers. If N is the number of rectangles in a test case, 2 <= N <= 1,000,000 -10^15 <= Xmin < Xmax <= +10^15 -10^15 <= Ymin < Ymax <= +10^15 Input ends with an end of file. The test case name line is at most 80 characters. Output ------ For each test case, first an exact copy of the test case name line. Then just one line giving the number of pairs of rectangles which overlap. Two rectangles overlap if and only if they have an interior point in common. For example, [0,2]x[4,5] and [1,3]x[2,8] overlap as they have the intersection [1,2]x[4,5] which has an interior, but [0,2]x[4,5] and [2,4]x[2,8] do not overlap as they have the intersection {2}x[4,5] which has no interior. Sample Input ------ ----- -- SAMPLE 1 -- 1 3 0 4 2 4 1 5 3 5 2 6 * -- SAMPLE 2 -- 0 10 -10 -0 1 11 -11 -1 2 12 -12 -2 3 13 -13 -3 4 14 -14 -4 5 15 -15 -5 6 16 -16 -6 7 17 -17 -7 8 18 -18 -8 9 19 -19 -9 * -- SAMPLE 3 -- -10 +10 -5 +5 -10 +10 -5 +5 -10 +10 -5 +5 -10 +10 -5 +5 -10 +10 -6 +6 * Sample Output ------ ------ -- SAMPLE 1 -- 2 -- SAMPLE 2 -- 45 -- SAMPLE 3 -- 10 File: overlap.txt Author: Bob Walton Date: Fri Oct 5 05:41:13 EDT 2018 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.