Moisil++ 2023 Clasele 11-12 Mirror | TrapEZZ

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 $n$ puncte în plan. Găsiți numărul de trapeze isoscele care se pot forma cu punctele date.

$ABDC$ este un trapez isoscel dacă:

1. $AB\text{ }||\text{ }CD$
2. $dist(A,C)=dist(B,D)$
3. $A,B,C,D$ nu sunt coliniare
4. $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 $n$.

Pe fiecare dintre următoarele $n$ linii se vor afla câte două numere întregi $x_i$ și $y_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

• $4 \le n \le 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 $10$ puncte, $n \le 50$ și $0 \le y_i \le 1$;
• Pentru încă $10$ puncte, $n \le 300$ și $0 \le y_i \le 1$;
• Pentru încă $10$ puncte, $0 \le y_i \le 1$;
• Pentru încă $30$ de puncte, $n \le 50$;
• Pentru încă $20$ de puncte, $n \le 300$;
• Pentru încă $10$ puncte, oricare două puncte $i$ și $j$ au $x_i \neq x_j$ și $y_i \neq y_j$;
• Pentru restul de $10$ 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 $ADHG$, $BDIF$ și $CDIG$.

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 $7$ trapeze isoscele sunt: $AKHC$, $BJIC$, $DGHE$, $CEFD$, $DFKJ$, $CDJF$ și $DKFE$.