Fişierul intrare/ieşire:dmg.in, dmg.outSursăStelele Informaticii 2005, clasele 11-12
AutorSorin Stancu-MaraAdăugată de
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Dmg

Max Damage s-a trezit intr-o zi pe varful stancii sale ... s-a uitat in zare si a vazut ca politia i-a dat de urma. Fuga nu ar fi o problema, oricum are o masina mai buna, dar Max doreste sa se distreze un pic. El stie ca daca ar merge de-a lungul unei drepte, politistii (care pot fi considerati niste puncte) ar cauta drumul minim pana la directia sa de mers, chiar daca s-ar intersecta cu aceasta mult dupa ce Max a trecut. Asa ca Max se gandeste daca nu cumva ii poate face pe politisti sa se loveasca doi cate doi, unul de celalalt (drumurile celor doi sa aiba directii opuse si sa se intersecteze cu drumul lui Damage in acelasi timp si in acelasi loc). Evident ca Max nu isi pune pune problema daca isi strica masina, deci drumul sau poate trece si prin politististi; evident, acestia sunt loviti de Damage deci nu mai trebuie sa se loveasca de nimeni. Din fericire, Max are un calculator de bord si ne-a trimis un email cuprinzand pozitiile politistilor. El cere un program care sa ii spuna in cate feluri poate realiza ceea ce si-a propus.

Cerinta

Cate traiectorii care satisfac cerintele lui Max Damage exista si care sunt acestea.

Date de Intrare

Prima linie a fisierului dmg.in contine un numar intreg N reprezentand numarul de politisti. Urmatoarele N linii contin cate doua numere reale cu 8 zecimale, Xi, Yi reprezintand pozitia unui politist.

Date de Iesire

Fisierul de iesire dmg.out va contine numarul de traiectorii posibile pentru masina lui Max. Urmatoarele linii contin fiecare cate trei numere reale cu 8 zecimale, A, B si C, ce descriu o traiectorie de ecuatie A*X + B*Y + C = 0, ce indeplineste conditiile dorite de Max.

Restrictii si precizari

  • 2 ≤ N ≤ 1500
  • |Xi| ≤ 1000, |Yi| ≤ 1000
  • Max Damage nu e foarte "stiintific" si va verifica daca dreapta indeplineste conditiile sale cu o precizie de 0.01
  • Pentru 25% din teste N ≤ 100
  • Ce se intampla daca doi politisti sunt in acelasi punct ?
  • Politistii se deplaseaza cu aceeasi viteza constanta

Exemplu

dmg.indmg.out
2
0 0
10 0
2
-10.00000000 -0.00000000 50.00000000
0.00000000 -5.00000000 0.00000000

Explicatii

Max Damage poate merge perpendicular pe dreapta Ox, iar cei doi politisti se vor lovi la pozitia (0,5), sau poate merge pe dreapta Ox lovind masinile celor doi politisti. Orice alta dreapta nu indeplineste cerintele lui Max.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content