Rectangle Counting

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.2s

Python 1.6s

Memory limit: 256M

Author:

Plasmatic

Problem type

In the sport of rectangle counting, participants are given a set of $N$ $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$ $N$ rectangles. Her schedule is very busy so she doesn't have the time to do all the calculations, can you help her?

Constraints

Note that the corners of the $i^\text{th}$ $i^{th}$ rectangle are $(a_i, b_i)$ $(a_{i}, b_{i})$ and $(c_i, d_i)$ $(c_{i}, d_{i})$ .

$1 \le N \le 2 \times 10^5$ $1 \leq N \leq 2 \times 10^{5}$

$1 \le a_i, b_i, c_i, d_i \le 10^6$ $1 \leq a_{i}, b_{i}, c_{i}, d_{i} \leq 10^{6}$

Note the difference in constraints above.

$a_i < c_i$ $a_{i} < c_{i}$

$b_i < d_i$ $b_{i} < d_{i}$

Subtask 1 [15%]

$1 \le N \le 2 \times 10^3$ $1 \leq N \leq 2 \times 10^{3}$

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line of input contains the integer $N$ $N$ .

The next $N$ $N$ lines of input each contain $a_i, b_i, c_i, d_i$ $a_{i}, b_{i}, c_{i}, d_{i}$ , representing the corners of the $i^\text{th}$ $i^{th}$ rectangle.

Output Specification

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

Sample Input

Copy

Sample Output

Copy

Sample Explanation

The intersecting pairs of rectangles are:

$(1, 2)$ $(1, 2)$
$(2, 3)$ $(2, 3)$

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

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

Comments

1

andrewtam commented on Feb. 3, 2021, 3:40 p.m.

If a rectangle is contained entirely within another and their perimeters do not intersect, do they still count as an intersecting pair? For example, {(1, 1), (5, 5)} and {(3, 3), (4, 4)}.

1

julian33 commented on Jan. 26, 2022, 1:30 a.m.

for those wondering, the answer to this question is yes. i think a better description of the problem is to count the number of overlapping pairs.