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.