Fişierul intrare/ieşire:agora.in, agora.outSursăONI 2018, clasa a 10-a, ziua 2
AutorChiorean Tudor-OctavianAdăugată deGabiTulbaGabi Tulba-Lecu GabiTulba
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Agora

Prietenul nostru, Pit, se află în Grecia antică, în cea mai vestită piaţă publică. Considerăm că piaţa este un dreptunghi din plan, de dimensiuni X şi Y. Dacă reprezentăm piaţa într-un reper cartezian xOy, aceasta are cele patru vârfuri în punctele de coordonate (0,0), (X,0), (X,Y) şi (0,Y). În fiecare punct (a,b), cu a ∈ {1,...,X} şi b ∈ {1,...,Y}, se află câte o tarabă care vinde echere. Prietenul nostru este afacerist şi vrea să închirieze o parcelă de teren dreptunghiulară, având laturile paralele cu laturile pieţei, iar cele patru vârfuri de coordonate numere naturale. Vârfurile parcelei se află în interiorul pieţei sau pe laturile acesteia. În această parcelă, Pit vrea să cuprindă cât mai multe tarabe speciale, care au următoarele proprietăţi:

  • distanta de la origine la tarabă este număr natural;
  • nu există nici o altă tarabă pe segmentul dintre origine şi tarabă.

Cerinta

Cunoscându-se valorile X, Y şi coordonatele (Sxi, Syi) şi (Dxi, Dyi) pentru Q parcele, unde 1≤i≤Q, să se afle, pentru fiecare parcelă, care este numărul de tarabe speciale pe care le conţine.

Date de intrare

Pe primul rând al fişierului agora.in se află trei numere naturale despărţite prin câte un spaţiu, X, Y şi Q , cu semnificaţia din enunţ. Pe următoarele Q rânduri se află câte 4 numere naturale nenule Sxi , Syi , Dxi , Dyi, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Date de ieşire

Pe fiecare dintre primele Q rânduri ale fişierului agora.out se va afla câte un număr natural, numărul de pe linia i reprezentând numărul tarabelor speciale conţinute de către parcela i.

Restricţii

  • 2 ≤ X ≤ 7000
  • 2 ≤ Y ≤ 7000
  • 1 ≤ Q ≤ 100.000
  • o tarabă face parte dintr-o parcelă şi dacă se află pe laturile ei;
  • (Sxi, Syi) şi (Dxi,Dyi) nu se vor afla în afara dreptunghiului asociat pieţei, dar se pot afla pe laturile lui;
  • Pentru teste în valoare de 10 puncte: X, Y ≤ 100 şi Q ≤ 100
  • Pentru alte teste în valoare de 20 puncte: X, Y ≤ 2000 şi Q ≤ 1000
  • Pentru alte teste în valoare de 10 puncte: X, Y ≤ 2000 şi Q ≤ 100.000
  • Punctele speciale care trebuie numarate au coordonata x intre Sxi si Dxi (inclusiv capetele), in timp ce coordonata y trebuie sa fie intre Dyi si Syi (inclusiv capetele)
  • Sxi ≤ Dxi
  • Dyi ≤ Syi

Exemplu

agora.inagora.out
5 5 2
1 5 3 4
3 4 4 3
1
2

Explicaţie

Prima parcelă conţine taraba specială de la punctul (3,4).
A doua parcelă conţine tarabele speciale (3,4) şi (4,3)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?