Editing 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).
== Exemplul 1 ==
; Intrare
: 15 2 3 5 2 30 20 50 100
; Ieșire
: 55
<br>
== Exemplul 2 ==
; Intrare
: 8 1 1 1 1 2 1 3 10
; Ieșire
: 6
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#4267 - Perechi Puncte
def generate_coordinates(n, x1, y1, x2, y2, A, B, C, D):
    coordinates = [(x1, y1), (x2, y2)]

    for i in range(3, n + 1):
        xi = (coordinates[i - 1][0] * A + coordinates[i - 2][0] * B + C) % D
        yi = (coordinates[i - 1][1] * A + coordinates[i - 2][1] * B + C) % D
        coordinates.append((xi, yi))

    return coordinates

def count_symmetric_pairs(coordinates):
    point_count = {}
    symmetric_pairs = 0

    for point in coordinates:
        symmetric_pairs += point_count.get((point[1], point[0]), 0)
        point_count[point] = point_count.get(point, 0) + 1

    return symmetric_pairs

def main():
    n, x1, y1, x2, y2, A, B, C, D = map(int, input().split())

    if not (10 <= n <= 6_000_000 and 0 <= x1 <= 30_000 and 0 <= y1 <= 30_000 and 0 <= x2 <= 30_000 and 0 <= y2 <= 30_000 and 2 <= A <= 30_000 and 2 <= B <= 30_000 and 2 <= C <= 30_000 and 2 <= D <= 30_000):
        print("Fals")
        return

    coordinates = generate_coordinates(n, x1, y1, x2, y2, A, B, C, D)
    result = count_symmetric_pairs(coordinates)

    print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>