An Animal Contest 5 P5 - Counting Rectangles

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 3.0s
Java 6.0s
Memory limit: 256M

Author:
Problem types

Larry the magical panda got bored of playing with his number game, and now he is playing with bamboo sticks instead! Each stick has a non-zero integer length and can be classified as either a horizontal or vertical line on a coordinate plane. A horizontal stick has a left endpoint at (x_{i1}, y_i) and a right endpoint at (x_{i2}, y_i). A vertical stick has a bottom endpoint at (x_i, y_{i1}) and a top endpoint at (x_i, y_{i2}). Due to the peculiar shape of the sticks, some horizontal or vertical sticks may overlap with each other. In total, Larry has H horizontal and V vertical bamboo sticks.

Larry then notices that his current arrangement of sticks can form rectangles! More precisely, a selection of 4 distinct sticks is considered to form a rectangle if the sticks intersect at 4 distinct points and form a rectangle with positive area. Being a curious panda, Larry wants to find the total number of rectangles that can be formed. Please help him find this number!

Constraints

1 \le H, V \le 5 \times 10^3

-10^9 \le x, y, x_{i1}, x_{i2}, y_{i1}, y_{i2} \le 10^9

x_{i1} < x_{i2}

y_{i1} < y_{i2}

Subtask 1 [20%]

1 \le H, V \le 400

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains two integers H and V.

The next H lines each contain three integers y_i, x_{i1}, x_{i2}.

The next V lines each contain three integers x_i, y_{i1}, y_{i2}.

Output Specification

Output the number of rectangles that can be formed on a single line.

Sample Input 1

2 2
2 -1 3
0 -1 3
1 -2 4
2 -2 4

Sample Output 1

1

Sample Input 2

4 3
2 0 6
-1 1 6
-1 -3 3
1 2 4
0 -2 4
3 -2 6
6 -1 2

Sample Output 2

2

Explanation for Sample Output 2

The two rectangles (denoted by bottom left and top right corner) are \{(0,-1), (3,2)\} and \{(3,-1), (6,2)\}.

Sample Input 3

4 4
2 0 2
2 0 2
0 0 2
0 0 2
0 0 2
0 0 2
2 0 2
2 0 2

Sample Output 3

16

Comments

There are no comments at the moment.