Rectangle Counting

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.2s
Python 1.6s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

In the sport of rectangle counting, participants are given a set of N rectangles and race to count the number of intersecting pairs. In order to check the answer, judges are called in to verify that the number of pairs counted by each contestant is correct.

The other day, Angie was invited to judge one of the competitions and now has to produce the correct answer for today's set of N rectangles. Her schedule is very busy so she doesn't have the time to do all the calculations, can you help her?


Note that the corners of the i^{th} rectangle are (a_i, b_i) and (c_i, d_i).

1 \le N \le 2 \times 10^5

1 \le a_i, b_i, c_i, d_i \le 10^6

Note the difference in constraints above.

a_i < c_i

b_i < d_i

Subtask 1 [15%]

1 \le N \le 2 \times 10^3

Subtask 2 [85%]

No additional constraints.

Input Specifications

The first line of input contains the integer N.

The next N lines of input each contain a_i, b_i, c_i, d_i, representing the corners of the i^{th} rectangle.

Output Specifications

Output the number of pairs of rectangles that intersect with one another. Note that two pairs (x, y) and (y, x) are considered the same pair and that two rectangles that are merely touching do not count as intersecting.

Sample Input

1 7 10 12
5 3 15 9
14 5 16 10
16 1 17 20

Sample Output


Sample Explanation

The intersecting pairs of rectangles are:

  • (1, 2)
  • (2, 3)

Note that the pairs (2, 1) and (3, 2) aren't counted.

Furthermore, even though the pair (3, 4) is touching they aren't counted because they don't fully intersect.


  • 5
    Plasmatic  commented on Nov. 10, 2019, 9:24 a.m.

    Made TL more python-friendly