1819B - The Butcher - CodeForces Solution

/**
 * The Butcher
 * Codeforces Rd 866 (Div 1)
 * Problem B
 * url: https://codeforces.com/problemset/problem/1819/B
 * date: 5/28/23
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(ll a, ll b, map<ll, multiset<ll>> &a_d, map<ll, multiset<ll>> &b_d) {
    // cout << "DEBUG----------------------------------------------------------------------\\\n";
    // cout << "a: " << a << ", b: " << b << '\n';
    // cout << "a_d: \n";
    // for (auto el : a_d) {
    //     cout << "  " << el.first << ": ";
    //     for (auto i : el.second) {
    //         cout << i << " ";
    //     }
    //     cout << '\n';
    // }
    // cout << "b_d: \n";
    // for (auto el : b_d) {
    //     cout << "  " << el.first << ": ";
    //     for (auto i : el.second) {
    //         cout << i << " ";
    //     }
    //     cout << '\n';
    // }
    // cout << "END_DEBUG------------------------------------------------------------------/\n\n";

    if (a == 0 || b == 0) return true;

    if (a_d[a].size() > 0) {
        ll b_c = *a_d[a].rbegin();
        a_d[a].erase(prev(a_d[a].end()));
        b_d[b_c].erase(prev(b_d[b_c].end()));

        bool res = check(a, b - b_c, a_d, b_d);

        if (res) return true;
    }

    if (b_d[b].size() > 0) {
        ll a_c = *b_d[b].rbegin();
        b_d[b].erase(prev(b_d[b].end()));
        a_d[a_c].erase(prev(a_d[a_c].end()));

        bool res = check(a - a_c, b, a_d, b_d);

        if (res) return true;
    }

    return false;
}

bool check_wrapper(ll a, ll b, map<ll, multiset<ll>> a_d, map<ll, multiset<ll>> b_d) {
    return check(a, b, a_d, b_d);
}


int main () {
    ll t; cin >> t;

    // if (t != 8480) {

        while (t--) {
            ll n; cin >> n;
            vector<ll> a(n), b(n);
            ll a_max = -1, b_max = -1;
            ll area = 0;
            map<ll, multiset<ll>> a_d, b_d;
            for (ll i = 0; i < n; i++) {
                cin >> a[i] >> b[i];
                a_max = a[i] > a_max ? a[i] : a_max;
                b_max = b[i] > b_max ? b[i] : b_max;
                a_d[a[i]].insert(b[i]);
                b_d[b[i]].insert(a[i]);
                area += (ll) a[i] * b[i];
            }
            vector<pair<ll, ll>> sols;
            ll b_c = area / a_max;
            if (b_c * a_max == area) {
                // cout << a_max << ' ' << b_c << '\n';
                if (check_wrapper(a_max, b_c, a_d, b_d)) sols.push_back({a_max, (ll) b_c});
            }
            ll a_c = area / b_max;
            if (a_c * b_max == area) {
                if (check_wrapper(a_c, b_max, a_d, b_d)) {
                    if (a_c != a_max) sols.push_back({(ll) a_c, b_max});
                };
            }
            cout << sols.size() << '\n';
            for (auto i : sols) {
                cout << i.first << ' ' << i.second << '\n';
            }
        }

    // } else {
    //     for (int i = 0; i < t; i++) {
    //         bool printing = (i == 439 || i == 440); 
    //         if (printing) cout << i << '\n';
    //         ll n; cin >> n;
    //         if (printing) cout << n << '\n';
    //         ll a, b;
    //         for (ll i = 0; i < n; i++) {
    //             cin >> a >> b;
    //             if (printing) cout << a << ' ' << b << '\n';
    //         }
    //     }
    // }
}