.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » zoo

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
zoo


Timp maxim de executie/test:
0.5 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Fermierul Ion are idee originala: sa infiinteze pe teritoriul fermei sale gradina zoologica "Madame Tussaud". Si fiindca deja are o colectie impresionanta de animale de ceara, in marime naturala, raspandite pe teritoriul fermei sale acest lucru nu e foarte dificil.
In acest scop a luat harta fermei sale, pe care este fixat un sistem de coordonate si pe care sunt marcate pozitiile animalelor pe teritoriul fermei. Fiecare animal este plasat pe teritoriul fermei într-un punct de coordonate întregi si nu poate fi mutat fara a-l deteriora.
Gradina zoologica pe care o proiecteaza Ion va avea forma unui dreptunghi având laturile paralele cu axele de coordonate si Ion ar dori ca aceasta sa contina cat mai multe animale.
Înainte de a începe constructia, fermierul face un studiu, pentru a gasi pozitia optima de amplasare a gradinii zoologice. Pentru aceasta, el si-a ales câteva pozitii unde ar putea sa construiasca gradina zoologica. Pentru fiecare dintre ele, ar dori sa stie câte animale dintre cele N pe care le are se afla în interiorul gradinii (sau pe marginile acesteia).

Cerinta

Scrieti un program care sa determine pentru fiecare amplasare posibila a gradinii zoologice numarul de animale care s-ar afla in interiorul acesteia (sau pe margini).

Date de intrare

Prima linie a fisierului de intrare zoo.in contine numarul întreg N, reprezentând numarul de animale. Fiecare dintre urmatoarele N linii contine coordonatele x si y ale unui animal, separate prin spatiu. Urmatoarea linie contine numarul întreg M, reprezentând numarul posibilitatilor de amplasare a gradinii zoologice. Pe fiecare dintre urmatoarele M linii se afla patru numere întregi separate prin spatii: x1 y1 x2 y2 unde (x1,y1) reprezinta coordonatele coltului stânga-jos al gradinii zoologice, iar (x2,y2) reprezinta coordonatele coltului dreapta-sus.

Date de iesire

În fisierul zoo.out veti afisa, pentru fiecare posibilitate de amplasare a gradinii zoologice, numarul de animale aflate în interiorul sau pe marginile acesteia.

Restrictii

  • 1 <= N <= 16 000
  • 1 <= M <= 100 000
  • Coordonatele fiecarui animal si ale colturilor fiecarui dreptunghi sunt numere întregi din intervalul [-2 000 000 000 , 2 000 000 000].
  • Pot exista mai multe animale în acelasi punct.
  • x1<x2 si y1<y2 pentru fiecare dreptunghi descris în fisierul de intrare

Exemplu

zoo.in

zoo.out
5
0 0
1 0
2 0
0 1
1 1
3
0 0 1000 1000
-1000 -1000 0 0
1 0 2 2
5
1
3

Mugurel Andreica
Universitatea Politehnica Bucuresti

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la Şansa de a deveni campion 2002: adevar, marcare, joc10, prieteni1, bare, soricel1, traseu, zapezi, banda10, soricel2, masina2, excursie1, asmax, salvare, perechi1, culmi, tramvai1, numar2, sume1, raft, bloc, schi, joc12, sediu, soricel3, ferma, fni, sah1, suma3, granita, nr4, fractie, blockout, join, cod3, tunel, lover, trip, pepsi, string, medii, transport, tren3, avion, prime1, poligon1, monkey, premii1, garaj, carti2, gramada, microvirus, tv, gramezi1, puncte2, benzina, aranjari, numere5, fat, izo, cafea, top, echipe1, secvente
De acelaşi autor: autobuze, bile, complex, balaur, vmem, kreg, ro, jobs, senzori, echipe, agitatie, center, algebra, tgraf, bcast, promo, asmax, sediu, granita, string, poligon1, csir, lsort, bombo, ab3, soc, rsp, tcast, tj, lanterna, base3, color, trans, ic, xp, v2d, ppcover, carray, asfalt1, module, gxor
Despre geometrie: forum, supertri, ozn, detinut, atac, afise, mere, ff, teren, volei, aven, patrate, robot, pahare, pendul, robot2, dragon, poligon, druid, laser, patrate3, ploaia, donald, lot, atac1, arcas, paralel, dotnet, aedaro, vectori, spirala, distanta, triunghi, center, harta1, seceta, antena, poligon1, benzina, texan, oypara, dreptc, mosia, sea, poligon3, poligon2, snipers, basm, cetati, placa, nori, cerc, smin, cern, cuiburi, acerc, select, proiect, poligon4, terenuri, monoton, acoperire, capra, testament, jb, sdmin, ozn1, parc1, gsm, triunghi5, puncte6, romb1, dreapta, grindina, tdrept
Despre arbori: bonuri, tgv, barfa, votare, arce, balaur, trains, bile2, vmem, plopi, caravane, mese, strict, tree, sub, kinder, firma1, albinuta, rlcs, masina, omizi, concurs1, latime, piloti, barca1, arbnr, sirag1, pikachu, arb, logn, maxq, arbore, bcast, mesaj1, traseu, asmax, salvare, tramvai1, omida, sediu, string, tv, izo, ratina, vitale, camion1, arbfind, cezar1, tcast, dep, curent, spp, frunze, sea2, culori, color, urgenta, nori, treegame, antipatie, scanduri, minuni, arb1, activ, regat, kdtree, autostrazi, carray, trenuri1, arbgraf, war, mess, secvnumber, subs, posta, radare, arbore1, hacker, lista, codarb, subsecvente, confuzie, transform, arbsum, copaci3, arbvalmax
surse trimise | ajutor