COCI 2006/2007, Contest #6

Task PROSTOR

A long time ago in a three-dimensional space far away, a tribe of rectangles lived happily. The rectangles lived a spiritual life, parallel with one of the coordinate planes.

One day, a cuboid walked into their small world, riding steadily on an icosahedron, showing off its sharp corners and positive volume. The rectangles watched in awe and dreamed of being cuboids. Nothing would ever be the same from that day on. The rectangles started comparing each other by area, perimeter and even by the ratio of the lengths of their sides.

Soon the first conflict ensued over the ownership of shared points. In time, each pair of rectangles sharing at least one point (including those merely touching each other) got into a conflict and became enemies.

It is up to you to restore peace in the community, by meeting with every pair of rectangles in conflict. Write a program that finds how many such pairs there are.

Input

The first line of input contains the integer N (1 ≤ N ≤ 100 000), the number of rectangles.

Each of the following N lines contains 6 integers separated by single spaces. The first three numbers represent the coordinates of one corner of the rectangle, the other three are the coordinates of the opposite corner.

The coordinates are integers between 1 and 999 (inclusive).

Each rectangle is parallel to one of the coordinate planes, meaning that in exactly one of the three dimensions, the two corresponding coordinates will be equal.

Output

Output the total number of rectangles in conflict on a single line.

Sample Tests

3
1 1 1 1 3 3
1 3 3 1 6 6
1 4 4 1 5 5

2

3
15 10 10 15 20 20
10 15 10 20 15 20
10 10 15 20 20 15

3

5
4 4 5 4 3 2
5 3 2 4 3 1
5 4 3 1 1 3
1 4 3 1 5 4
5 5 4 5 4 2

4

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Aug 13, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can anyone tell me why test cases 9 and 10 are giving me a RE? It seems to work when I run it locally...

You potentially go out of bounds on log2d::a, since your update function loops <= MAX. Just add one to each dimension and it works perfectly.

Incidentally, SIGSEGVs reported by judge are never incorrectly done so; it works fine locally because your computer is more tolerant of illegal accesses :P