Fişierul intrare/ieşire:meteor.in, meteor.outSursăONI 2004 clasa a 8-a
AutorAdrian Nita, Maria NitaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Meteor (clasa a 8-a)

Pe planeta UZABU, va cădea o ploaie de meteoriţi. Savanţii ştiu că fiecare meteorit este de formă dreptunghiulară, având laturile paralele cu axele de coordonate (şi pe planeta UZABU axele de coordonate au aceeaşi semnificatie ca şi pe Pământ). Solul planetei este reprezentat prin axa OX. Meteoriţii căzuţi pe planetă sunt folositori pentru agricultură. Dacă un meteorit în cădere atinge un alt meteorit atunci amândoi se vor distruge iar craterul format distruge solul planetei.

Cerinţă

Cunoscând care sunt coordonatele plăcilor date prin patru numere (x1, y1, x2, y2), cu semnificaţia: (stânga_sus_x, stânga_sus_y, dreapta_jos_x, dreapta_jos_y), savanţii trebuie să distrugă o parte dintre meteoriţi astfel încât ei să nu se suprapună în momentul atingerii solului.

Date de intrare

Fişierul de intrare meteor.in are structura :

  • Pe prima linie N reprezentând numărul de meteoriţi
  • Pe următoarele N linii câte patru numere separate prin câte un spaţiu, reprezentând coordonatele stânga sus şi dreapta jos ale plăcii dreptunghiulare. 

Date de ieşire

Fişierul de ieşire meteor.out conţine o singură valoare k reprezentând numărul maxim al plăcilor rămase.

Restricţii

  • Numărul de plăci meteoritice N: 0 ≤ N ≤ 500
  • Coordonatele fiecărui meteorit sunt numere întregi 0 ≤ x, y ≤ 32000
  • Două plăci care prin cădere se lipesc nu se distrug.

Exemplu

meteor.inmeteor.out
10
5 10 18 2
15 22 27 12
35 30 40 25
43 30 45 25
32 20 45 12
50 20 60 15
20 30 30 25
65 20 82 15
48 13 75 2
78 14 100 3
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici