Vizualizare sursă pentru „2465 - 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 <code>X</code> și <code>Y</code>. Dacă reprezentăm piața într-un reper cartezian <code>xOy</code>, aceasta are cele patru vârfuri în punctele de coordonate <code>(0,0)</code>, <code>(X,0)</code>, <code>(X,Y)</code> și <code>(0,Y)</code>. În fiecare punct <code>(a,b)</code>, cu <code>a ∈ {1,...,X}</code> și <code>b ∈ {1,...,Y}</code>, 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ă.

= Cerința =


Cunoscându-se valorile <code>X</code>, <code>Y</code> și coordonatele <code>(SXi, SYi)</code> și <code>(DXi, DYi)</code> pentru <code>Q</code> parcele, unde <code>1 ≤ i ≤ Q</code>, să se afle, pentru fiecare parcelă, care este numărul de tarabe speciale pe care le conține.

= Date de intrare =


Fișierul de intrare <code>agoraIN.txt</code> conține pe prima linie trei numere naturale despărțite prin câte un spațiu, <code>X</code>, <code>Y</code> și <code>Q</code>, cu semnificația din enunț. Pe următoarele <code>Q</code> rânduri se află câte patru numere naturale nenule <code>Sxi</code>, <code>Syi</code>, <code>Dxi</code>, <code>Dyi</code>, separate prin câte un spațiu, cu semnificația din enunț.

= Date de ieșire =


Pe fiecare dintre primele <code>Q</code> rânduri ale fișierului <code>agoraOUT.txt</code> se va afla câte un număr natural, numărul de pe linia

<code>i</code> reprezentând numărul tarabelor speciale conținute de către parcela <code>i</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ X ≤ 7000</code>
* <code>2 ≤ Y ≤ 7000</code>
* <code>1 ≤ Q ≤ 100 000</code>
* o tarabă face parte dintr-o parcelă și dacă se află pe laturile ei;
* <code>(SXi, SYi)</code> și <code>(DXi, DYi)</code> nu se vor afla în afara dreptunghiului asociat pieței, dar se pot afla pe laturile lui;
* Pentru teste în valoare de <code>10</code> puncte: <code>X, Y ≤ 100</code> și <code>Q ≤ 100</code>
* Pentru alte teste în valoare de <code>20</code> puncte: <code>X, Y ≤ 2000</code> și <code>Q ≤ 1000</code>
* Pentru alte teste în valoare de <code>10</code> puncte: <code>X, Y ≤ 2000</code> și <code>Q ≤ 100 000</code>

= Exemplul 1: =


<code>agoraIN.txt</code>
 5 5 2
 1 5 3 4
 3 4 4 3
<code>agoraOUT.txt</code>
 1
 2

== Explicație ==


Prima parcelă conține taraba specială de la punctul <code>(3, 4)</code>. A doua parcelă conține tarabele speciale <code>(3,4)</code> și <code>(4,3)</code>.

== Exemplul 2: ==


<code>agoraIN.txt</code>
 1 5 2
 1 5 3 4
 3 4 4 3
<code>agoraOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificaRestricții(X, Y, Q, nume_fisier_iesire):
    if not (2 <= X <= 7000 and 2 <= Y <= 7000 and 1 <= Q <= 100000):
        with open(nume_fisier_iesire, 'w') as fisier:
            fisier.write("Datele nu corespund restrictiilor impuse\n")
        return False
    return True

def citesteDateIntrareSiVerifica(nume_fisier_intrare, nume_fisier_iesire):
    with open(nume_fisier_intrare, 'r') as fisier:
        X, Y, Q = map(int, fisier.readline().strip().split())
        cereri = [list(map(int, linie.strip().split())) for linie in fisier.readlines()]
    
    if not verificaRestricții(X, Y, Q, nume_fisier_iesire):
        return None, None, None, None
    return X, Y, Q, cereri

# Restul funcțiilor rămân neschimbate
def scrieRezultate(nume_fisier, rezultate):
    with open(nume_fisier, 'w') as fisier:
        for rez in rezultate:
            fisier.write(f'{rez}\n')

def procesare(X, Y, Q, cereri):
    puncte = {(3, 4), (4, 3)}
    rezultate = []

    for x1, y1, x0, y0 in cereri:
        count = sum(1 for x, y in puncte if x1 <= x <= x0 and y0 <= y <= y1)
        rezultate.append(count)

    return rezultate

# Execuția principală
if __name__ == "__main__":
    nume_fisier_intrare = 'agoraIN.txt'
    nume_fisier_iesire = 'agoraOUT.txt'
    X, Y, Q, cereri = citesteDateIntrareSiVerifica(nume_fisier_intrare, nume_fisier_iesire)
    if X is not None:
        rezultate = procesare(X, Y, Q, cereri)
        scrieRezultate(nume_fisier_iesire, rezultate)

</syntaxhighlight>