== include(page="template/taskheader" task_id="dmg") ==
==Include(page="template/taskheader" task_id="dmg")==
Poveste ...
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.
h2. Cerinta
...
Cate traiectorii care satisfac cerintele lui Max Damage exista si care sunt acestea.
h2. Restrictii
h2. 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, $X{~i~}, Y{~i~}$ reprezintand pozitia unui politist.
h2. Date de intrare
h2. 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.
h2. Date de iesire
h2. Restrictii si precizari
...
* $2 ≤ N ≤ 1500$
* $|X{~i~}| ≤ 1000, |Y{~i~}| ≤ 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
h2. Exemplu
| dmg.in | dmg.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. dmg.in |_. dmg.out |
| 2
0 0
10 0
| 2
-10.00000000 -0.00000000 50.00000000
0.00000000 -5.00000000 0.00000000 |
h3. 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.
==Include(page="template/taskfooter" task_id="dmg")==
== include(page="template/taskfooter" task_id="dmg") ==
