3489 - Numara punctele

Cerința

Considerăm o suprață plană în formă de pătrat având latura de 100 de unități și două mulțimi:

• Mulțimea P de puncte având coordonatele numere reale pozitive mai mici decat 100 (deci aparținând pătratului).
• Mulțimea ordonată C de cercuri având centrul în același pătrat și cu raza variabilă (se poate întâmpla ca centrul să fie în punctul p(1,1) și cercul să aibă raza de 3, deci să aibă o porțiune înafara pătratului).

Se dorește să se stabilească, pentru fiecare dintre cercurile din mulțimea C, câte puncte din mulțimea P se află în interior (sau pe marginea acestuia).

Date de intrare

Programul citește de la tastatură numărul n de puncte, iar apoi n cupluri de numere reale, separate prin spații reprezentând coordonatele fiecărui punct. După ce a citit valorile reprezentând coordonatele punctelor, se va citi numărul m de cercuri și vor apoi cele m triplete reprezentând coordonatele centrului cercului respectiv raza cercului.

Date de ieșire

În cazul în care datele sunt valide, se va afișa un mesaj de confirmare, iar pentru fiecare cerc citit se va afișa pe câte o linie diferită câte puncte sunt in interiorul său sau pe frontieră. În caz contrar, se va afișa un mesaj de eroare.

Restricții și precizări

• 1≤n≤100000
• Pentru fiecare punct p(x,y) avem x∈[0,100] respectiv y∈[0,100]
• 1≤m≤10000
• Pentru fiecare cerc c(x,y,r) avem x∈[0,100], y∈[0,100] și r∈[0,30]

Exemplu

Intrare

3

6.39 24.96

6.23 6.17

20.0 20.0

3

23.05 83 10.57

15.00 15.00 10.0

10.0 20.0 10

Ieșire

0

1

2

Explicație

S-au introdus 3 puncte și 3 cercuri.

Cercul 1: c1(23.05,83,10.57) nu conține niciun punct deoarece coordonata sa y este prea mare, raza de 10.57 fiind insuficientă pentru a ajunge la cele trei puncte care au coordonate relativ mici (distantele de la centrul cercului la cele trei puncte sunt de 78.65, 60.38, 63.07, toate valorile fiind mai mari decat raza).

Cercul 2: c2(15.00,15.00,10.0) contine p3(20,20). Distanța de la centru la acest punct este de 7.07, distanță mai mică decât raza cercului (de 10.0). Deci punctul se află în cerc. Distanțele de la centrul lui c2 până la p1 și p2 sunt de 12.45 respectiv de 13.17.

Cercul 3: c3(10.0,20.0,10) contine p1(6.39,24.96). Distanța de la centru la acest punct este de 6.14, distanță mai mică decât raza cercului (de 10.0). De asemenea conține punctul p3(20,20), distanța de la acesta la centrul cercului fiind exact cât raza cercului. Distanță de la c3 la p2 este de 14.34 (deci mai mare decât raza lui c3).

Concluzia este că cercul 1 conține 0 puncte, al doilea cerc conține 1 punct iar cel de-al treilea cerc coține 2 puncte – de aici și rezultatul.

Rezolvare

<syntaxhighlight lang="python"> def validare(n: int, puncte: list[tuple[float, float]], m: int, cercuri: list[tuple[float, float, float]]) -> bool:

   # verificam numarul de puncte si de cercuri
   if not 1 <= n <= 100000 or not 1 <= m <= 10000:
       return False

   # verificam coordonatele punctelor si ale cercurilor
   for p in puncte:
       if not 0 <= p[0] <= 100 or not 0 <= p[1] <= 100:
           return False

   for c in cercuri:
       if not 0 <= c[0] <= 100 or not 0 <= c[1] <= 100 or c[2] <= 0:
           return False

   return True

def numar_puncte_in_cercuri(puncte, cercuri):

   numar_puncte = []
   for cerc in cercuri:
       num_puncte_in_cerc = 0
       for punct in puncte:
           distanta = ((punct[0] - cerc[0]) ** 2 + (punct[1] - cerc[1]) ** 2) ** 0.5
           if distanta <= cerc[2]:
               num_puncte_in_cerc += 1
       numar_puncte.append(num_puncte_in_cerc)
   return numar_puncte

if __name__ == "__main__":

   # citirea numarului de puncte
   n = int(input())
   # citirea coordonatelor fiecarui punct
   puncte = []
   for i in range(n):
       x, y = input().split()
       x = float(x)
       y = float(y)
       puncte.append((x, y))
   # citirea numarului de cercuri
   m = int(input())
   # citirea coordonatelor si razei fiecarui cerc
   cercuri = []
   for i in range(m):
       x, y, r = input().split()
       x = float(x)
       y = float(y)
       r = float(r)
       cercuri.append((x, y, r))
   # validarea datelor introduse
   if validare(n, puncte, m, cercuri):
       print("Datele introduse sunt corecte.")
       # numarul de puncte din interiorul fiecarui cerc
       numar_puncte = numar_puncte_in_cercuri(puncte, cercuri)
       # afisarea numarului de puncte din interiorul fiecarui cerc
       for i in numar_puncte:
           print(i)
   else:
       print("Unul sau mai multe numere introduse nu sunt valide.")

</syntaxhighlight>

Explicație cod

Acest cod are două funcții definite și o secțiune principală de cod.

Funcția `validare` primește ca argumente un număr întreg `n`, o listă de perechi de coordonate (x,y) reprezentând punctele și un număr întreg `m` și o listă de tupluri (x,y,r) reprezentând cercurile. Funcția verifică dacă numărul de puncte și cercuri este în limitele permise și dacă coordonatele și razele cercurilor sunt valide (în intervalul 0-100). În cazul în care aceste condiții nu sunt îndeplinite, funcția returnează `False`, altfel returnează `True`.

Funcția `numar_puncte_in_cercuri` primește ca argumente lista de puncte și cea de cercuri și returnează o listă cu numărul de puncte din fiecare cerc.

În secțiunea principală de cod, mai întâi se citește numărul de puncte, apoi coordonatele fiecărui punct, apoi numărul de cercuri și coordonatele și razele acestora. După aceea se validează datele introduse. În cazul în care sunt valide, se afișează mesajul "Datele introduse sunt corecte." și se calculează numărul de puncte din fiecare cerc cu ajutorul funcției `numar_puncte_in_cercuri`, iar apoi se afișează numărul de puncte din fiecare cerc. În caz contrar, se afișează mesajul "Unul sau mai multe numere introduse nu sunt valide.".