Suprafaţa plană a unei mese de pseudo-biliard este formată din nxn celule pătratice cu lungimea laturii egală cu 1 (o unitate), lipite, dispuse pe n linii numerotate de la 1 la n şi n coloane, numerotate de la 1 la n. Pe masă se aşează K bile, fiecare bilă găsindu-se în centrul unei anumite celule a mesei. Un jucător doreşte să plaseze pe suprafaţa mesei un cadru pătratic având lungimea diagonalei egală cu D unităţi.
El trebuie să răspundă la m întrebări de forma: x y. Fiecare întrebare are semnificaţia: câte bile se găsesc în interiorul sau pe laturile cadrului ?
Cadrul se plasează astfel încât fiecare colţ să fie poziţionat în centrul unei celule, colţurile opuse să se găsească pe aceeaşi coloană, respectiv pe aceeaşi linie, iar colţul “de sus” să fie plasat în centrul celulei aflată pe linia x şi coloana y.
Cerinţă
Cunoscând lungimea n a laturilor mesei, numărul m de întrebări, numărul K de bile aşezate pe masă, poziţiile lor şi lungimea D a diagonalei cadrului pătratic, se cere:
1. Numărul de celule care se vor găsi în întregime în interiorul cadrului, dacă acesta se aşează pe suprafaţa mesei, conform descrierii de mai sus.
2. Câte un răspuns pentru fiecare dintre cele m întrebări.
Date de intrare
Fişierul de intrare pseudobil.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele naturale n, K şi D separate prin câte un spaţiu.
Pe fiecare dintre următoarele K linii, se găsesc câte două numere a şi b (a, b ≤ n) reprezentând linia şi coloana celulei în centrul căreia va fi aşezată o bilă.
Pe linia K + 3 se găseşte un număr natural m.
Următoarele m linii conţin câte două numere naturale x şi y, reprezentând linia şi coloana celulei în centrul căreia se va plasa colţul „de sus” al cadrului.
Date de ieşire
Dacă valoarea lui p este 1, se va rezolva numai punctul 1 din cerinţă. În acest caz, în fişierul de ieşire pseudobil.out se va scrie un singur număr natural n1, reprezentând numărul de celule care se vor găsi în întregime în interiorul cadrului.
Dacă valoarea lui p este 2, se va rezolva numai punctul 2 din cerinţă. În acest caz, fişierul de ieşire pseudobil.out va conţine m linii. Pe fiecare linie i se va scrie câte un număr natural n2, reprezentând răspunsul pentru întrebarea i.
Restricţii
• 3 ≤ n ≤ 1500
• 1 ≤ K ≤ 55 000
• 2 ≤ D ≤ n – 1 , D – număr par
• 1 ≤ m ≤ 100 000
• Poziţiile cadrului sunt distincte.
• Se garantează pentru x şi y valori pentru care cadrul este plasat în interiorul suprafeţei mesei de pseudo-biliard.
Exemple
pseudobil.in
pseudobil.out
Explicaţii
1
5 2 4
3 4
5 2
1
1 3
5
p = 1
n = 5, K = 2, D = 4
D = (3 unităţi + 2*0.5 unităţi) = 4
Numărul de celule aflate în întregime în interiorul cadrului este n1 = 5
Atenţie! Pentru acest test se rezolvă doar cerinţa 1.
Se observă că în acest caz este suficient să se citească datele aflate pe primele două linii.
2
6 5 4
2 3
1 1
5 6
4 4
3 5
2
1 3
2 4
3
2
p = 2, n = 6, K = 5, D = 4.
Prima întrebare este: 1 3 . Sunt două bile pe laturile cadrului şi una în interior, deci n2 = 3
A doua întrebare este: 2 4. O bilă se găseşte pe una dintre laturile cadrului şi una în interior, deci n2 = 2
Atenţie! Pentru acest test se rezolvă doar cerinţa 2.
