TrapEZZ

Time limit: 4s Memory limit: 256MB Input: trapezz.in Output: trapezz.out

Din cauza restricțiilor de buget, minerul Gaudeamus nu a putut să se intoarcă și la această ediție de Moisil++. Prin urmare, el v-a pregătit următoarea urare:

Cerință

Se dau coordonatele a nn puncte în plan. Găsiți numărul de trapeze isoscele care se pot forma cu punctele date.

ABDCABDC este un trapez isoscel dacă:

  1. AB  CDAB\text{ }||\text{ }CD
  2. dist(A,C)=dist(B,D)dist(A,C)=dist(B,D)
  3. A,B,C,DA,B,C,D nu sunt coliniare
  4. dist(A,B)dist(C,D)dist(A,B) \neq dist(C,D) (altminteri trapezul ar fi un paralelogram).

Date de intrare

Pe prima linie a fișierului de intrare trapezz.in se va afla numărul de puncte nn.

Pe fiecare dintre următoarele nn linii se vor afla câte două numere întregi xix_i și yiy_i - coordonatele punctelor date.

Date de ieșire

Fișierul de ieșire trapezz.out va conține numărul de trapeze isoscele care se pot forma cu punctele date.

Restricții și precizări

  • 4n10004 \le n \le 1000;
  • 1000xi,yi,1000-1000 \le x_i,y_i, \le 1000;
  • Toate punctele din fișierul de intrare sunt distincte;
  • Atenție la erorile de precizie și la numele fișierelor!;
  • Pentru 1010 puncte, n50n \le 50 și 0yi10 \le y_i \le 1;
  • Pentru încă 1010 puncte, n300n \le 300 și 0yi10 \le y_i \le 1;
  • Pentru încă 1010 puncte, 0yi10 \le y_i \le 1;
  • Pentru încă 3030 de puncte, n50n \le 50;
  • Pentru încă 2020 de puncte, n300n \le 300;
  • Pentru încă 1010 puncte, oricare două puncte ii și jj au xixjx_i \neq x_j și yiyjy_i \neq y_j;
  • Pentru restul de 1010 puncte, nu se impun restricții suplimentare.

Exemplul 1

trapezz.in

9
0 0
1 0
2 0
3 0
4 0
0 1
1 1
2 1
4 1

trapezz.out

3

Explicație


Cele trei trapeze isoscele sunt ADHGADHG, BDIFBDIF și CDIGCDIG.

Exemplul 2

trapezz.in

11
-3 -3
-3 -2
-2 0
-1 -2
-1 3
1 4
2 -1
2 2
3 0
4 -2
5 1

trapezz.out

7

Explicație


Cele 77 trapeze isoscele sunt: AKHCAKHC, BJICBJIC, DGHEDGHE, CEFDCEFD, DFKJDFKJ, CDJFCDJF și DKFEDKFE.

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