题目大意：
给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。
思路：
枚举矩形的安放顺序，再按照题目所给的图判断即可，主要要想到枚举。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int i,n,sum=10009,p[5],q[5],a[5],b[5]; 4 struct data { int x,y; }ans[10000]; 5 bool used[5]; 6 7 bool cmp(data a,data b) { return a.x<b.x; } 8 9 void pd(int l,int r) 10 { 11 if (l*r<sum) 12 { 13 sum=l*r,ans[n=1].x=l,ans[1].y=r; 14 if (l>r) swap(ans[1].x,ans[1].y); 15 return; 16 } 17 if (l*r==sum) 18 { 19 ans[++n].x=l,ans[n].y=r; 20 if (l>r) swap(ans[n].x,ans[n].y); 21 } 22 } 23 24 void dfs(int k) 25 { 26 if (k>4) 27 { 28 int l=0,r=0,i; 29 for (i=1;i<5;i++) l=max(l,p[i]),r+=q[i]; 30 pd(l,r);//1 31 for (l=r=0,i=1;i<4;i++) l=max(l,p[i]),r+=q[i]; 32 pd(l+p[4],max(r,q[4]));//2 33 l=max(p[1],p[2])+p[3],r=max(q[1]+q[2],q[3]); 34 pd(max(l,p[4]),r+q[4]);//3 35 l=max(p[1],p[2]),r=max(q[3],q[4]); 36 pd(l+p[3]+p[4],max(r,q[1]+q[2]));//5 37 l=max(p[1]+p[2],p[3]+p[4]); 38 if (q[1]>=q[2]) 39 if (q[4]>q[3]) pd(l,q[1]+q[4]); 40 else 41 if (p[1]+p[3]<=l) pd(l,max(q[1]+q[4],q[2]+q[3]));//6 42 return; 43 } 44 for (int i=1;i<5;i++) 45 if (!used[i]) 46 { 47 used[i]=1; 48 p[k]=a[i],q[k]=b[i],dfs(k+1); 49 p[k]=b[i],q[k]=a[i],dfs(k+1); 50 used[i]=0; 51 } 52 } 53 54 int main() 55 { 56 for (i=1;i<5;i++) scanf("%d%d",&a[i],&b[i]); 57 dfs(1),sort(ans+1,ans+n+1,cmp),printf("%d\n",sum); 58 printf("%d %d\n",ans[1].x,ans[1].y); 59 for (i=2;i<=n;i++) 60 if (ans[i].x!=ans[i-1].x) printf("%d %d\n",ans[i].x,ans[i].y); 61 return 0; 62 }
转载于:https://www.cnblogs.com/HHshy/p/6013295.html
