Paralelogrami

ļoti grūts
Latvijas Informātikas olimpiādes logo
Uzdevums no Latvijas 38. (2024./2025. m.g.) informātikas olimpiādes (LIO) valsts kārtas; vecākajai (11.-12. klašu) grupai.

Stāsts

Šajā uzdevumā aplūkosim paralelogramus, kuru virsotnes atrodas Dekarta koordinātu plaknē punktos ar veselām koordinātām. Atkarībā no paralelograma virsotņu novietojuma, arī tā diagonāļu krustpunkts var atrasties punktā ar veselām koordinātām.

Piemēram, ja paralelograma virsotnes atrodas punktos ar koordinātām (4;2)(-4;-2), (2;2)(-2;2), (8;4)(8;4) un (6;0)(6;0), tad tā diagonāļu krustpunkts atrodas punktā ar koordinātām (2;1)(2;1).

Uzrakstiet datorprogrammu, kas nosaka, cik dažādos veidos no dotajiem NN punktiem ar veselām koordinātām var izvēlēties četrus punktus tā, ka šī paralelograma diagonāles krustojas koordinātu sākumpunktā (0;0)(0;0).

Ievaddati

Pirmajā rindā dots punktu skaits - naturāls skaitlis NN (4N51054 \leq N \leq 5 \cdot 10^5). Nākamajās NN rindās katrā dotas viena punkta koordinātas (abscisa un ordināta) - divi veseli skaitļi xix_i un yiy_i, kur 109xi,yi109-10^9 \leq x_i, y_i \leq 10^9. Starp skaitļiem ievaddatos ir tukšumzīme. Visi dotie plaknes punkti ir savā starpā atšķirīgi.

Izvaddati

Izvaddatu vienīgajā rindā jābūt veselam nenegatīvam skaitlim - atšķirīgo veidu skaitam, kā no NN dotajiem punktiem izvēlēties četrus ar aprakstītajām īpašībām. Punktu četrinieki, kuros atšķiras tikai punktu secība, netiek uzskatīti par atšķirīgiem.

Piemēri

Ievaddati

4 -1 -1 2 2 -1 2 2 -1 Kopēt kodu

Izvaddati

0 Kopēt kodu

Ievaddati

8 -4 -2 -2 2 8 4 6 0 4 2 2 -2 -6 0 -8 -4 Kopēt kodu

Izvaddati

5 Kopēt kodu

Piezīme:

Šie paralelogrami ir: 1: (-8;-4),(-2;2),(8;4),(2;-2) 2: (-8;-4),(-6;0),(8;4),(6;0) 3: (-6;0),(-2;2),(6;0),(2;-2) 4: (-4;-2),(-2;2),(4;2),(2;-2) 5: (-4;-2),(-6;0),(4;2),(6;0). Ievērojiet, ka neder punktu četrinieks (-8;-4),(-4;-2),(8;4),(4;2), jo šāda četrstūra pretējās malas nav paralēlas - tām ir kopīgi punkti.

Izpildes resursu ierobežojumi

CPU izpildes laiks uz testu: 1.6 sekundes.
RAM atmiņas apjoms uz testu: 256 megabaiti.

Apakšuzdevumi un to vērtēšana

#Apakšuzdevuma aprakstsPunkti
1.

Nav papildu ierobežojumu.

2
2.

Tiek izmantots uzdevuma tekstā dotais tests.

20
3.

4N1004\leq N \leq 100

20
4.

104xi,yi104-10^4 \leq x_i, y_i \leq 10^4

28
5.

101N1000101\leq N \leq 1000

30
Apakšuzdevumu punktu summa = 100.

1. apakšuzdevuma ievaddati

11 2 6 1 3 3 3 -1 2 2 2 -1 -1 -2 -2 1 -2 -1 -3 2 -4 -2 -6 Kopēt kodu