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

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ă.

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

<syntaxhighlight> 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 </syntaxhighlight>

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

def 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
   validare(n, puncte, m, cercuri)
   # 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)

if __name__ == "__main__":

   main()

</syntaxhighlight>