| Fișierul intrare/ieșire | meteor.in, meteor.out | Sursă | ONI 2004 clasa a 8-a |
|---|---|---|---|
| Autor | Adrian Niță | Maria Niță | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
| Scorul tău | N/A | Dificultate |
  2
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
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 semnificație 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.in | meteor.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 |
