==Include(page="template/taskheader" task_id="dmg")==

==Include(page="template/taskheader" task_id="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.
 
h2. Cerinta
 
Cate traiectorii care satisfac cerintele lui Max Damage exista si care sunt acestea.
 
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 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. 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
 
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/raw")==
 
Link: [1]File-List
 
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 2 cate 2, unul de celalalt (drumurile celor 2 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. 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 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. Restrictii si precizari
 
o 2 <= N <= 1500
o |X[i]| <= 1000, |Y[i]| <= 1000
o Max Damage nu e foarte "stiintific" si va verifica daca dreapta indeplineste conditiile sale cu o precizie de 0.01
o Pentru 25% din teste N <= 100
o Ce se intampla daca 2 politisti sunt in acelasi punct ?
o Politistii se deplaseaza cu aceeasi viteza constanta
 
h2. Exemplu
 
Dmg.in dmg.out Explicatii
2 2 Max Damage poate merge perpendicular pe dreapta Ox, iar
cei doi politisti se vor lovi la pozitia (0,5), sau poate
0 0 -10.00000000 -0.00000000 50.00000000 merge pe dreapta Ox lovind masinile celor doi politisti.
Orice alta dreapta nu indeplineste cerintele lui Max.
10 0 0.00000000 -5.00000000 0.00000000
 
 
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/dmg/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="dmg")==

710