| Fişierul intrare/ieşire: | zoo.in, zoo.out | Sursă | .campion 2003 |
| Autor | Mugurel Ionut Andreica | Adăugată de | |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Zoo
Fermierul Ion are o 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 intr-un punct de coordonate intregi si nu poate fi mutat fara a-l deteriora. Gradina zoologica pe care o proiecteaza Ion va avea forma unui dreptunghi avand laturile paralele cu axele de coordonate si Ion ar dori ca aceasta sa contina cat mai multe animale. Inainte de a incepe constructia, fermierul face un studiu, pentru a gasi pozitia optima de amplasare a gradinii zoologice. Pentru aceasta, el si-a ales cateva pozitii unde ar putea sa construiasca gradina zoologica. Pentru fiecare dintre ele, ar dori sa stie cate animale dintre cele N pe care le are se afla in 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 intreg N, reprezentand numarul de animale. Fiecare dintre urmatoarele N linii contine coordonatele x si y ale unui animal, separate prin spatiu. Urmatoarea linie contine numarul intreg M, reprezentand numarul posibilitatilor de amplasare a gradinii zoologice. Pe fiecare dintre urmatoarele M linii se afla patru numere intregi separate prin spatii: x1 y1 x2 y2 unde (x1,y1) reprezinta coordonatele coltului stanga-jos al gradinii zoologice, iar (x2,y2) reprezinta coordonatele coltului dreapta-sus.
Date de iesire
In fisierul zoo.out veti afisa pentru fiecare posibilitate de amplasare a gradinii zoologice cate o linie pe care sefla numarul de animale aflate in interiorul sau pe marginile acesteia.
Restrictii si precizari
- 1 ≤ N ≤ 16.000
- 1 ≤ M ≤ 100.000
- Coordonatele fiecarui animal si ale colturilor fiecarui dreptunghi sunt numere intregi din intervalul [-2.000.000.000, 2.000.000.000]
- Pot exista mai multe animale in acelasi punct
- x1 < x2 si y1 < y2 pentru fiecare dreptunghi descris in fisierul de intrare
- Orice linie se termina cu Enter
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 |
