COCI '07 Contest 3 #4 Dejavu

View as PDF

Submit solution

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

Problem type
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

N points are placed in the coordinate plane.

Write a program that calculates how many ways we can choose three points so that they form a right triangle with legs parallel to the coordinate axes.

A right triangle has one 90-degree internal angle. The legs of a right triangle are its two shorter sides.

Input Specification

The first line of input contains the integer N (3 \le N \le 100\,000), the number of points. Each of the following N lines contains two integers X and Y (1 \le X, Y \le 100\,000), the coordinates of one point.

No pair of points will share the same pair of coordinates.

Output Specification

Output the number of triangles.


In 40\% of all test cases, N will be less than 100.

In 70\% of all test cases, N will be less than 10\,000.

Sample Input 1

4 2
2 1
1 3

Sample Output 1


Sample Input 2

1 2
2 1
2 2
2 3
3 2

Sample Output 2


Sample Input 3

10 10
20 10
10 20
20 20
30 20
30 30

Sample Output 3



There are no comments at the moment.