Fişierul intrare/ieşire:gold.in, gold.outSursăSummer Challenge 3
AutorAdrian Diaconu, Filip Cristian BuruianaAdăugată de
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Gold

Fie N mine cu aur aflate la puncte de coordonate intregi in plan. Fiecare mina contine o cantitate cunoscuta de aur, exprimata in kilograme. Doi cautatori de aur au venit in zona si doresc sa imparta minele intre ei. Pentru a le fi mai simplu, se hotarasc sa aleaga doua din cele N mine. Astfel, unele dintre cele N-2 mine ramase vor fi de o parte, iar altele de cealalta parte a dreptei formata de cele doua mine alese. Minele dintr-o zona vor fi repartizate primului cautator, urmand ca celelalte sa ajunga in posesia celui de-al doilea. Cantitatea de aur pentru fiecare cautator este data de suma cantitatilor de aur aflate in minele din posesia sa. Problema care se iveste este ca unul dintre cautatori poate avea mult mai mult aur decat celalalt. Totusi, cei doi ajung la un compromis: daca diferenta in modul dintre cele doua cantitati nu depaseste o valoare stabilita P , atunci impartirea se considera a fi una echitabila.

Cerinta

Sa se determine in cate moduri pot fi stabilite cele doua mine astfel incat impartirea sa fie una echitabila.

Date de Intrare

Prima linie a fisierului gold.in contine N, numarul de mine. Pe a doua linie se afla valoarea P, cu semnificatia din enunt. Linia a 3-a va contine N numere naturale nenule, al i-lea numar reprezentand cantitatea de aur din mina a i-a. Incepand cu linia a 4-a, vor fi descrise pozitiile minelor referitor la un sistem ortogonal de axe: pe fiecare linie se va gasi o pereche de numere intregi (x y), mai precis pe linia i+3 aflandu-se coordonatele pentru cea de a i-a mina.

Date de Iesire

Prima linie a fisierului gold.out contine numarul de moduri diferite de a alege doua mine dintre cele N pentru ca impartirea sa fie echitabila.

Restrictii si precizari

  • 4 ≤ N ≤ 1.024
  • 0 ≤ P ≤ 98.765
  • Cantitatile de aur din mine sunt numere naturale cuprinse in [1, 10.000]
  • Coordonatele minelor sunt numere intregi in [-16.000, 16.000]
  • Oricare trei mine sunt necoliniare

Exemplu

gold.ingold.out
7
5
4 7 8 6 4 6 7
3 10
2 3
8 1
10 4
7 1
7 3
9 8
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content