tdrept

Time limit: 0.1s Memory limit: 4MB Input: tdrept.in Output: tdrept.out

Se consideră NN puncte de coordonate întregi în sistemul de coordonate cartezian.

Cerință

Scrieţi un program care determină numărul de triunghiuri dreptunghice având vârfurile plasate în 33 dintre punctele date şi catetele respectiv paralele cu axele de coordonate.

Date de intrare

Fișierul de intrare tdrept.in conține pe prima linie numărul natural NN, care reprezintă numărul de puncte. Pe următoarele NN linii se află câte două numere naturale xx și yy, separate prin spaţiu, reprezentând coordonatele carteziene ale celor NN puncte (abscisa şi ordonata).

Date de ieșire

Fișierul de ieșire tdrept.out va conține o singură linie pe care va fi scris un număr natural reprezentând numărul de triunghiuri dreptunghice care respectă condiţiile din enunţ. Deoarece numărul de soluţii poate fi foarte mare, rezultatul va fi afişat modulo 666 013666 \ 013 (adică restul împărţirii rezultatului la 666 013666 \ 013).

Restricții și precizări

  • 3N100 0003 \leq N \leq 100 \ 000
  • 0x,y100 0000 \leq x, y \leq 100 \ 000
  • Cele NN puncte din fişierul de intrare sunt distincte două câte două.

Exemplul

tdrept.in

8
1 1
1 4
10 8
4 1
9 1
5 5
7 4
7 5

tdrept.out

5

Explicație

Triunghiurile dreptunghice formate sunt:

(1,1) (1,4) (4,1)
(1,1) (9,1) (1,4) 
(5,5) (7,4) (7,5)
(1,4) (7,4) (7,5)
(1,1) (1,4) (7,4)

Log in or sign up to be able to send submissions!