include

include

define HASH_SIZE 100003

typedef struct Node { long long numerator; long long denominator; long long count; struct Node* next; } Node;

Node* hash_table[HASH_SIZE] = {NULL};

// Function to calculate GCD using Euclidean algorithm long long gcd(long long a, long long b) { while (b != 0) { long long temp = b; b = a % b; a = temp; } return a; }

// Hash function for reduced fraction unsigned int hash(long long a, long long b) { return ((a * 1000003LL + b) % HASH_SIZE); }

// Insert reduced fraction into hash table void insert(long long num, long long den) { unsigned int idx = hash(num, den); Node* curr = hash_table[idx];

while (curr != NULL) {
    if (curr->numerator == num && curr->denominator == den) {
        curr->count++;
        return;
    }
    curr = curr->next;
}

Node* new_node = (Node*)malloc(sizeof(Node));
new_node->numerator = num;
new_node->denominator = den;
new_node->count = 1;
new_node->next = hash_table[idx];
hash_table[idx] = new_node;

}

// Function to count nearly similar rectangles long long nearlySimilarRectangles(int sides[][2], int n) { long long total_pairs = 0;

for (int i = 0; i < n; i++) {
    long long a = sides[i][0];
    long long b = sides[i][1];
    long long g = gcd(a, b);

    long long reduced_a = a / g;
    long long reduced_b = b / g;

    insert(reduced_a, reduced_b);
}

// Count pairs
for (int i = 0; i < HASH_SIZE; i++) {
    Node* curr = hash_table[i];
    while (curr != NULL) {
        if (curr->count >= 2) {
            total_pairs += (curr->count * (curr->count - 1)) / 2;
        }
        curr = curr->next;
    }
}

return total_pairs;

}

// Example usage int main() { int sides[][2] = { {5, 10}, {10, 10}, {3, 6}, {9, 9} };

int n = sizeof(sides) / sizeof(sides[0]);
printf("%lld\n", nearlySimilarRectangles(sides, n));  // Output: 2

return 0;

}