In the sport of rectangle counting, participants are given a set of 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 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 rectangle are and .
Note the difference in constraints above.
Subtask 1 [15%]
Subtask 2 [85%]
No additional constraints.
The first line of input contains the integer .
The next lines of input each contain , representing the corners of the rectangle.
Output the number of pairs of rectangles that intersect with one another. Note that two pairs and are considered the same pair and that two rectangles that are merely touching do not count as intersecting.
4 1 7 10 12 5 3 15 9 14 5 16 10 16 1 17 20
The intersecting pairs of rectangles are:
Note that the pairs and aren't counted.
Furthermore, even though the pair is touching they aren't counted because they don't fully intersect.