An Animal Contest 5 P5 - Counting Rectangles

View as PDF

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 and a right endpoint at . A vertical stick has a bottom endpoint at and a top endpoint at . Due to the peculiar shape of the sticks, some horizontal or vertical sticks may overlap with each other. In total, Larry has horizontal and vertical bamboo sticks.

Larry then notices that his current arrangement of sticks can form rectangles! More precisely, a selection of distinct sticks is considered to form a rectangle if the sticks intersect at 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!

Input Specification

The first line contains two integers and .

The next lines each contain three integers .

The next lines each contain three integers .

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 and .

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