COCI '06 Contest 6 #6 Prostor

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Specification

The first line of input contains the integer N\ (1 \le N \le 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 Specification

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

Sample Input 1

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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

3

Sample Input 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

Sample Output 3

4

Comments

There are no comments at the moment.