4267 - Perechi Puncte

Se dau n puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale (x, y), unde x și y sunt numere naturale. Spunem că două puncte (x, y) și (i, j) sunt simetrice dacă x = j și y = i.

Cerința

Să se determine numărul perechilor de puncte simetrice.

Date de intrare

Programul citește de la tastatură, separate prin spații, numerele naturale n, x1, y1, x2, y2, A, B, C, D, unde n este numărul de puncte, (x1, y1) sunt coordonatele primului punct, (x2, y2) sunt coordonatele celui de-al doilea punct, iar restul punctelor (x[i], y[i]) se generează după formulele:

• x[i] = (x[i - 1] * A + x[i - 2] * B + C) % D, i = 3..n
• y[i] = (y[i - 1] * A + y[i - 2] * B + C) % D, i = 3..n

Date de ieșire

Programul va afișa pe ecran numărul perechilor de puncte simetrice.

Restricții și precizări

• 10 ≤ n ≤ 6.000.000
• 0 ≤ x1, y1, x2, y2 ≤ 30.000
• 2 ≤ A, B, C, D ≤ 30.000
• Punctele generate nu sunt neapărat distincte. Dacă de exemplu se generează de 5 ori punctul (2,9) și de 7 ori punctul (9,2), atunci se obțin 5 * 7 = 35 de perechi simetrice.
• Simetricul punctului (x, x) este un alt punct (x, x).

Exemplu:

Intrare

15 2 3 5 2 30 20 50 100

Ieșire

55

Rezolvare

<syntaxhighlight lang="python" line="1"> def verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):

   if not (10 <= n <= 6000000):
       return False
   if not (0 <= X <= 30000 and 0 <= Y <= 30000 and 0 <= X_ <= 30000 and 0 <= Y_ <= 30000):
       return False
   if not (2 <= a <= 30000 and 2 <= b <= 30000 and 2 <= c <= 30000 and 2 <= d <= 30000):
       return False
   return True

def main():

   data = input("").split()
   
   n = int(data[0])
   X = int(data[1])
   Y = int(data[2])
   X_ = int(data[3])
   Y_ = int(data[4])
   a = int(data[5])
   b = int(data[6])
   c = int(data[7])
   d = int(data[8])
   
   if not verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
       print("Datele nu corespund restrictiilor impuse")
       return
   
   from collections import defaultdict
   points = defaultdict(int)
   
   points[(X, Y)] += 1
   points[(X_, Y_)] += 1
   
   simetrice = 0
   
   if X == Y_ and Y == X_:
       simetrice += 1
   
   for i in range(3, n + 1):
       x, y = X, Y
       X, Y = X_, Y_
       X_ = (X * a + x * b + c) % d
       Y_ = (Y * a + y * b + c) % d
       
       simetrice += points[(Y_, X_)]
       points[(X_, Y_)] += 1
   
   print(f"{simetrice}")

if __name__ == "__main__":

   main()

</syntaxhighlight>