Fişierul intrare/ieşire:pitici2.in, pitici2.outSursăGrigore Moisil 2008, clasa a 9-a
AutorCsaba PatcasAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pitici2

In satul piticilor sunt N case, numerotate de la 1 la N. Vrajitorul satului a aflat de la zana cea buna ca satul urmeaza sa fie atacat. Folosind un ingredient magic, el poate face invizibile casele piticilor pana trece pericolul si astfel satul ar fi salvat. Din pacate vrajitorul nu are suficient ingredient magic, necesar ascunderii intregului sat si nu mai are nici timp sa mai aduca ierburi din padure. Datorita felului in care actioneaza vrajile lui, el va putea face invizibile doar case care se situeaza de-a lungul a trei drepte (nu neaparat distincte).
Stabiliti daca satul va putea fi salvat. In caz afirmativ indicati dreptele de-a lungul carora se afla casele piticilor. Altfel spus, trebuie sa determinati dreptele care "acopera" casele piticilor.

Date de intrare

Pe prima linie a fisierului pitici2.in se afla un numar natural N, reprezentand numarul caselor. Pe urmatoarele N linii se afla cate doua numere intregi, reprezentand coordonatele caselor.

Date de iesire

  • In cazul in care casele piticilor nu pot fi "acoperite" de cel mult trei drepte, pe prima linie a fisierului pitici2.out se va scrie propozitia 'Piticii sunt in pericol.'.
  • Daca satul va fi salvat, pe prima linie a fisierul de iesire se va scrie propozitia 'Piticii se vor salva.'. Pe urmatoarele trei linii se vor scrie cate doua numere naturale, reprezentand numere de ordine de case, separate prin cate un spatiu, care determina dreptele de-a lungul carora se situeaza casele din sat.

Restrictii

  • 2 ≤ N ≤ 5000
  • Coordonatele caselor vor fi din intervalul [-30 000, 30 000]
  • Daca exista mai multe solutii, in fisier se va scrie una singura
  • Doua case nu se vor afla in acelasi punct

Exemplu

pitici2.inpitici2.out
7
0 0
0 1
0 2
1 1
2 2
2 0
1 0
Piticii se vor salva.
1 2
1 4
1 7

Explicatie

Dreapta care uneste casa 1 cu casa 2 acopera si casa 3. Dreapta care uneste casa 1 cu casa 4 acopera si casa 5. Dreapta care uneste casa 1 cu casa 7 acopera si casa 6.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content