Fișierul intrare/ieșire meteor.in, meteor.out Sursă ONI 2004 clasa a 8-a
Autor Adrian Niță | Maria Niță Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii