大意:有一个大矩形,每次可以横着切或者竖着切,给你n个小矩形,问你原来的大矩形的宽高
思路:可以发现,最多有两种可能,找到所给矩形的宽和高的最大值,模拟check()
知识点:LL H=*max_element(a.begin(), a.end());数组最大值
ve.emplace_back(H,area/H); pair<int,int> 装入
priority_queue<pair<int,int> > qh,qw; 优先队列从大到小
//去重
sort(ans.begin(), ans.end());
ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
代码:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
#define IOS cin.tie(nullptr)->sync_with_stdio(false);
#define endl "\n"
#define se second
#define fi first
#define mem(a,b) memset(a,b,sizeof a);
#define pri priority_queue<int,vector<int>,greater<int> >
#define low(a,b,c) lower_bound(a,a+b,c)-a;
#define upp(a,b,c) upper_bound(a,a+b,c)-a;
const int N=1e6+7;
void solve()
{
LL n;
cin>>n;
vector<LL> a(n),b(n);
LL area=0;
for(int i=0;i<n;i++)
{
cin>>a[i]>>b[i];
area+=a[i]*b[i];
}
vector<PLL> ve;
LL H=*max_element(a.begin(), a.end());
LL W=*max_element(b.begin(), b.end());
cout<<H<<" "<<W<<"\n";
ve.emplace_back(H,area/H);
ve.emplace_back(area/W,W);
vector<PLL> ans;
for(auto v : ve){
LL h=v.fi;
LL w=v.se;
if(w*h!=area) continue;
priority_queue<pair<int,int> > qh,qw;
for(int i=0;i<n;i++)
{
qh.emplace(a[i],i);
qw.emplace(b[i],i);
}
vector<bool> st(n);
while(h*w>0)
{
while(st[qh.top().se]) qh.pop();
while(st[qw.top().se]) qw.pop();
int i=-1;
if(qh.top().fi==h)
{
i=qh.top().se;
}
if(qw.top().fi==w)
{
i=qw.top().se;
}
if(i==-1) break;
st[i]=true;
if(a[i]==h)
{
w-=b[i];
}
else
{
h-=a[i];
}
}
// cout<<h<<" "<<w<<"\n";
if(h*w==0)
{
ans.emplace_back(v.fi,v.se);
}
}
sort(ans.begin(), ans.end());
ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << "\n";
for(auto v:ans)
cout<<v.fi<<" "<<v.se<<"\n";
}
int main()
{
IOS;
int t=1;
cin>>t;
while(t--)
{
solve();
}
return 0;
}