题意:已知一个矩形的长和宽分别是 a,b。 现在有n个矩形,让你从中挑出2个矩形,使得这两个矩形可以放进 初始给的矩形中 求最大面积
思路: 暴力枚举所有组合C(2,n),对每一组矩形,判断是否可以放。判断的过程是: 先放一个矩形在左下角,然后再各个地方尝试加另外一个矩形。 略带贪心,贪在第一个矩形放左下角,这样才能让空间尽可能大的留给第二个矩形
数据分析:1 ≤ n, a, b ≤ 100
复杂度:O(n^2)
#include <bits/stdc++.h>
using namespace std;
int n,a,b;
int maxx=-1;
struct node
{
int a,b;
}rec[200];
void check(int i,int j)
{
int x1=rec[i].a,y1=rec[i].b;
int x2=rec[j].a,y2=rec[j].b;
bool flag=false;
if(x1<=a && y1<=b) // 第一个矩阵正常放
{
if(b-y1 >=y2 && x2<=a)
flag=true;
if(x2 <= a-x1 && y2 <= b)
flag=true;
if(b-y1 >=x2 && y2<=a)
flag=true;
if(y2 <= a-x1 && x2 <= b)
flag=true;
}
if(y1 <= a && x1 <=b )// 第一个矩阵倒着放
{
if(b-x1 >=y2 && x2<=a)
flag=true;
if(x2 <= a-y1 && y2 <= b)
flag=true;
if(b-x1 >=x2 && y2<=a)
flag=true;
if(y2 <= a-y1 && x2 <= b)
flag=true;
}
if(flag)
{
maxx=max(maxx,x1*y1+x2*y2);
}
return ;
}
int main(void)
{
cin >> n>>a >> b;
for(int i=1;i<=n;i++)
scanf("%d%d",&rec[i].a,&rec[i].b);
for(int i=1;i<=n-1;i++) // 枚举所有组合
{
for(int j=i+1;j<=n;j++)
{
check(i,j);
}
}
if(maxx==-1) printf("0\n");
else cout << maxx << endl;
return 0;
}