Fişierul intrare/ieşire:	agora.in, agora.out	Sursă	ONI 2018, clasa a 10-a, ziua 2
Autor	Chiorean Tudor-Octavian	Adăugată de	Gabi Tulba-Lecu •GabiTulba
Timp execuţie pe test	0.175 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/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 (Sx_i, Sy_i) şi (Dx_i, Dy_i) 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 Sx_i , Sy_i , Dx_i , Dy_i, 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;
• (Sx_i, Sy_i) şi (Dx_i,Dy_i) 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 Sx_i si Dx_i (inclusiv capetele), in timp ce coordonata y trebuie sa fie intre Dy_i si Sy_i (inclusiv capetele)
• Sx_i ≤ Dx_i
• Dy_i ≤ Sy_i

Exemplu

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)

Cum se trimit solutii?