Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cercuri5.in, cercuri5.out | Sursă | ONIS 2014, Runda 4 |
| Autor | Vlad Duta | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cercuri5
Intr-un plan sunt desenate un numar oarecare de cercuri, toate avand raza R. Cunoscand toate perechile de puncte care determina intersectia a doua cercuri, determinati numarul minim de cercuri desenate. Pentru a simplifica problema vom ignora cazul in care cercurile sunt tangente. Totodata, oricare doua cercuri nu vor coincide.
Date de intrare
Fişierul de intrare cercuri5.in contine pe prima linie un numar natural T, numarul de teste. Urmeaza cele T teste astfel:
Pe prima linie din fiecare test se gasesc numarul natural R, raza cercurilor, precum si M, numarul de intersectii de cercuri. Urmeaza M linii a cate 4 numere reale x1, y1, x2, y2, unde (x1, y1) sunt coordonatele primului punct de intersectie, iar (x2, y2) ale celui de-al doilea.
Date de ieşire
În fişierul de ieşire cercuri5.out veti afisa in ordine pentru fiecare test cate o linie de forma "Case <t>: <n>" (fara ghilimele) unde <t> este numarul testului, iar <n> este numarul minim de cercuri desenate.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ R ≤ 1000
- 1 ≤ M ≤ 1 000 000
- |x|, |y| ≤ 20 000
Exemplu
| cercuri5.in | cercuri5.out |
|---|---|
| 1 5 2 3 4 3 -4 9 4 9 -4 | 3 |
Explicaţie
...
