1820D-The Butcher

题目链接：The Butcher

        首先我们可以知道所有的矩形中必然有一个矩形的长或者宽等于最终矩形的长或者宽，因此我们可以将最大的长和宽分开进行讨论，对应的就是第一刀的切法。如果第一刀竖着切，那么高相等，反之宽相等。

        那么接下来我们考虑如何分割了，可以用multiset来解决，如果当前是竖着切，那么此时应该把所有高为h的矩形都去除，那么w也相应减少，然后递推一个个枚举横着切和竖着切知道所有的矩形都枚举完。

        代码附上：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5+5;
int n,sum,max_h,max_w;
map<int,multiset<int>>mp[2];
map<int,multiset<int>>tmp[2];
struct node{
	int h,w;
};

bool check(int n1,int h,int w,int t){
	while(h>0&&w>0){
		int tot=0;
		if(t){//检查竖切是否成功，即将所有竖切部分删除
			for(auto &i:tmp[0][h]){
				tot+=i;//tot为w减少的部分
				n1--;//总个数减少
				tmp[1][i].erase(tmp[1][i].find(h));
			}
			w-=tot;
		}
		else{//横着切
			for(auto &i:tmp[1][w]){
				tot+=i;//tot为h减少的部分
				n1--;
				tmp[0][i].erase(tmp[0][i].find(w));
			}
			h-=tot;
		}
		t^=1;
		if(tot==0)return false;
	}

	if(n1==0)return true;
	return false;

}

void solve(){
	cin>>n;
	mp[0].clear();
	mp[1].clear();
	sum=0;
	max_h=max_w=0;
	for(int i=1;i<=n;i++){
		int x,y;cin>>x>>y;
		mp[0][x].insert(y);
		mp[1][y].insert(x);
		sum+=x*y;//记录面积
		max_h=max(max_h,x);
		max_w=max(max_w,y);
	}

	vector<node>ans;
	tmp[0]=mp[0],tmp[1]=mp[1];
	if(sum%max_h==0){//竖着切
		if(check(n,max_h,sum/max_h,1)){
			ans.push_back({max_h,sum/max_h});
		}
	}
	tmp[0]=mp[0],tmp[1]=mp[1];
	if(sum%max_w==0){//横着切
		if(check(n,sum/max_w,max_w,0)){
			ans.push_back({sum/max_w,max_w});
		}
	}
	
	if(ans.size()==1){
		cout<<1<<"\n";
		cout<<ans[0].h<<" "<<ans[0].w<<"\n";
	}
	else if(ans[0].h==ans[1].h&&ans[0].w==ans[1].w){
		cout<<1<<"\n";
		cout<<ans[0].h<<" "<<ans[0].w<<"\n";
	}
	else{
		cout<<2<<"\n";
		for(int i=0;i<2;i++){
			cout<<ans[i].h<<" "<<ans[i].w<<"\n";
		}
	}
	
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int t=1;cin>>t;
	while(t--){
		solve();
	}

	return 0;
}