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

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


Timp maxim de execuţie/test:
0.6 secunde
Memorie totală disponibilă/stivă:
64MB/4MB

Se dau N puncte în plan, cu coordonatele numere reale şi M dreptunghiuri definite prin coordonatele stânga-jos, dreapta-sus (în această ordine), numere întregi.

Cerinţă

Se cere determinarea numărului de puncte din setul iniţial care se află strict în interiorul fiecărui dreptunghi citit.

Date de intrare

Fişierul de intrare incadrare.in conţine pe prima linie două numere naturale N şi M, separate printr-un spaţiu, reprezentând numărul de puncte, respectiv numărul de dreptunghiuri. Pe următoarele N linii se găsesc câte două numere, x y, separate printr-un spaţiu, reprezentând abscisa şi ordonata câte unui punct. Pe următoarele M linii se găsesc câte 4 numere separate prin spaţiu, x1 y1 x2 y2 reprezentând coordonatele colţului stânga-jos, respectiv ale colţului dreapta-sus pentru câte un dreptunghi.

Date de ieşire

Fişierul de ieşire incadrare.out va conţine M linii; pe linia i se găseşte numărul de puncte din al i-lea dreptunghi din fişierul de intrare.

Restricţii

  • 1 <= N <= 100 000
  • 1 <= M <= 200 000
  • 0 <= coordonatele punctelor sunt numere <= 500
  • Coordonatele celor M dreptunghiuri sunt numere naturale.
  • Coordonatele celor N puncte sunt numere reale cu partea fracţionară nenulă.

Exemplu

incadrare.in incadrare.out
3 3
2.3000 4.3333
2.1232 3.2323
3.1321 3.1231
1 1 4 4
2 2 3 3
2 2 4 4
2
0
2
stud Alexandru Cazacu
Facultatea de Matematica si Informatică Bucuresti
infooltenia2013@gmail.com
propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la InfoOltenia 2013: boltz, triunghi5, descompunere, vectori1, aranjare1
Despre matrice: vopsea, harta, opmat, sarpe, light, magic2, tetris, origami, concurs, iepuras, tribile, criptmat, cutie, patrate, 3d, pajura, perspic, vecini2, livada, matrice3, kafka, erdos, grup, scor2, reteta2, rezervatie, scoici, tablou, game, stea, submatrix, cifru, jokes, oua, trecere, na, dotnet, renju, ghici, mere1, agitatie, lacuri, sotron, desen1, camion, ceas1, fibo, parc, excursia, matricea, zidar, joc6, log, concurs2, cladiri, dist, centru, robinson, cuburi2, joc8, joc9, romeo, adevar, soricel2, avere, joc11, vizibil, sah1, blockout, masina3, lsort, anticip, matrice1, evantai, spion, pereti, zumzi, roboti, placare, tabel, ocr, numere7, lacusta, becuri, sir5, flori, cartele, furnica, pavare, poarta, rj, peri, poligon2, sablon1, gradina, matrice4, poartas, balcon, submdisj, v, matrx, figura, neuroni, raze, roboti1, bila, iepurasi, colorare, mat, submatrix1, simetric1, plaja, xor2, guess, albine1, joct, alfabetar, stele, tablou1, alpinist, cladire, cri, grupe2, el, mahjong, sir9, acces, tort1, joc17, mesaj3, zar1, xy, poteci, avioane, broscute, safeu, acoperire1, radioactiv, robot4, lcdr, jb, slide, maxtri, dame, triunghi4, elicop, compresie, mijloc, cubulete, romb, medalion, bile6, zigzag, puncte5, intersectii, matd3, matrixdel, speed, seif1, traseu2, betasah, zona, latin, zmax, amestec, sudoku1, gradina1, spider, zone, bemo, rombul, interclasare, rebus1, tabla, arrows, pseudobil, patrat1, rascoala, harta2, relatii, lasere, defrag, matcnt, ssdj, cript, ssk, teren1, fence, cifre6
surse trimise | ajutor