The problem can be found here

My Thought Process

Let’s start from the $h * w$ rectangle and then cut some pieces to see if we notice any pattern. If we have a $13*7$ rectangle like the last test case, and if we cut the first piece, what would the lengths of the first piece be?

Well, the problem states that the piece that will be cut will be $(h-x) * w$ or $h * (w-y)$. So that mean we will get two pieces thats either

\[(h-x) * w \text{ and } x * w\]

or

\[h * (w-y) \text{ and } h * y\]

Okay, so we would always have one piece with height or width being one of the lengths of the starting rectangle. That mean that either the biggest length or width out of all the rectangles should be one of the lengths of the starting rectangle. Looking at the last testcase again, $(8, 7)$ have both the biggest width and height so the starting rectangle can be $8*y$ or $x * 7$. The output of $(13, 7)$ confirms this.

That seems like an important piece of information. How can we use these to find the other possible side? Well, we have all the rectangles so that mean we have the total area. Since we have a side, we can find the other side.

Now, all there left to do is to test the two possible starting rectangles. If the other side isn’t an integer, we can discard that. So for example, $8 * y = 91$ but $91$ isn’t divisible by $91$ so this isn’t possible.

We can also see that after the first cut, you will be left with a rectangle thats $x*y$ and similar to before, the next rectangle cut will have one of its side be $x$ and $y$ since its basically the same thing as before.

See the implementation for more information.

Implementation

$l$ keeps track of rectangles with $x$ values as its key. $r$ keeps track of rectangles with $y$ values as its key.

The check function sees if there are rectangles matching a side length of the current rectangle, if there are, we erase it from both the maps and readjust the rectangle to its new dimensions.

Essentially, we are starting from a possible rectangle and repeately subtracting areas of rectangle from it until we end up with a filled rectangle.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

#define int long long

bool check(map<int, multiset<pair<int, int>>> l, map<int, multiset<pair<int, int>>> r, int x, int y){
    while(true){
        if(l[x].size() > 0){
            auto a = *l[x].begin();
            l[x].erase(l[x].find(a));
            r[a.second].erase(r[a.second].find(a));
            y = y - a.second;
        }
        else if(r[y].size() > 0){
            auto b = *r[y].begin();
            r[y].erase(r[y].find(b));
            l[b.first].erase(l[b.first].find(b));
            x = x - b.first;
        }
        else{
            break;
        }
    }

    if(x == 0 || y == 0){return true;}
    return false;
}

void solve() { 
    int n;
    cin >> n;
    map<int, multiset<pair<int, int>>> l;
    map<int, multiset<pair<int, int>>> r;

    int area = 0;
    int x = 0;
    int y = 0;
    for(int i = 0; i < n; ++i){
        int a, b; cin >> a >> b;
        l[a].insert({a,b});
        r[b].insert({a, b});
        
        x = max(x, a);
        y = max(y, b);
        area += (a * b);
    }

    set<pair<int, int>> ans;

    if(area % x == 0){
        if(check(l, r, x, area/x)){
            ans.insert({x, area/x});
        }
    }

    if(area % y == 0){
        if(check(l, r, area/y, y)){
            ans.insert({area/y, y});
        }
    }

    cout << ans.size() << endl;
    for(auto i : ans){
        cout << i.first << ' ' << i.second << endl;
    }


}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.