题目链接:https://codeforces.com/contest/1820/problem/D
比赛的时候读错题了,没看见他切一刀之后会把其中一个放进盒子里(也就是不能再切了)。
思路:首先原来的大矩形的其中一边肯定在盒子里的小矩形的其中一边里(也就是说答案最多只有两种),我们先找出最大的长和宽(选择其中一个作为第一刀是切长还是宽),接着模拟切的过程就行了。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef pair<long long,long long>P;
set<P>ans;
map<long long,multiset<int>>xx,yy;
bool check(long long X,long long Y,int c,map<long long,multiset<int>>a,map<long long,multiset<int>>b){
while(X>0&&Y>0){
bool flag = 0;
if (c){
for (auto s:a[X]){
flag = 1;
Y -= s;
b[s].erase(b[s].find(X));
}
c = 0;
}else{
for (auto s:b[Y]){
flag = 1;
X -= s;
a[s].erase(a[s].find(Y));
}
c = 1;
}
if (!flag) return false;
}
return X == 0 || Y == 0;
}
void solve(){
xx.clear();
yy.clear();
ans.clear();
int n;
cin>>n;
long long mxh = 0,mxw = 0;
long long sum = 0;
for (int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
sum += 1ll*x*y;
mxh = max(mxh,y*1ll);
mxw = max(mxw,x*1ll);
xx[x].insert(y);
yy[y].insert(x);
}
if ((sum%mxw==0)&&check(mxw,sum/mxw,1,xx,yy)) ans.insert({mxw,sum/mxw});
if ((sum%mxh==0)&&check(sum/mxh,mxh,0,xx,yy)) ans.insert({sum/mxh,mxh});
cout<<ans.size()<<'\n';
for (auto s:ans) cout<<s.first<<' '<<s.second<<'\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
cin>>T;
while(T--) solve();
return 0;
}