题意：给你四个矩形，给你6种基本摆放，问你如何摆放使得他们能够不重叠放入一个面积最小的矩形里面，求出这个矩形的面积以及它的所有情况
解题思路：枚举所有情况，情况4和情况5可以合并，状态压缩枚举所有的长宽状态以及位置，就可求得
解题代码：
1 // Packing Rectangles.cpp : 定义控制台应用程序的入口点。 2 // 3 4 //#include "stdafx.h" 5 6 /* 7 ID: dream.y1 8 PROG: packrec 9 LANG: C++ 10 */ 11 12 #include <cstdio> 13 #include <cstring> 14 #include <cmath> 15 #include <cstdlib> 16 #include <algorithm> 17 18 using namespace std; 19 20 struct node{ 21 int x, y ; 22 }p[5],q[5],a[10000]; 23 int ans = 100000000; 24 int sum = 0 ; 25 int ms1,ms2; 26 int num[6]; 27 void ok() // 对答案进行添加 28 { 29 if(ms1*ms2 < ans) 30 { 31 ans = ms1*ms2; 32 sum = 1; 33 memset(a,0,sizeof(a)); 34 if(ms1 > ms2) 35 { 36 a[sum].x = ms2; 37 a[sum].y = ms1; 38 } 39 else 40 { 41 a[sum].x = ms1; 42 a[sum].y = ms2; 43 } 44 }else if(ms1*ms2 == ans) 45 { 46 sum ++; 47 if(ms1 > ms2) 48 { 49 a[sum].x = ms2; 50 a[sum].y = ms1; 51 } 52 else 53 { 54 a[sum].x = ms1; 55 a[sum].y = ms2; 56 } 57 } 58 } 59 int mx(int x, int y ) 60 { 61 if(x > y ) 62 return x; 63 else return y; 64 } 65 int hehe1() 66 { 67 ms1 = 0 ; 68 ms2 = 0; 69 for(int i =1;i <= 4;i ++) 70 { 71 ms1 = mx(ms1,q[i].x); 72 ms2 += q[i].y; 73 } 74 return 1; 75 } 76 int hehe2() 77 { 78 ms1 = 0 ; 79 ms2 = 0 ; 80 int tempc = 0; 81 int tempg = 0; 82 for(int i = 1;i <= 3; i ++) 83 { 84 tempc +=q[num[i]].x; 85 } 86 for(int i = 1;i <= 3;i ++) 87 { 88 tempg= mx(tempg,q[num[i]].y); 89 } 90 ms1 = tempg + q[num[4]].x; 91 ms2 = mx(tempc,q[num[4]].y); 92 return 1; 93 } 94 int hehe3() 95 { 96 ms1 = 0 ; 97 ms2 = 0 ; 98 ms1 = mx(q[num[2]].x + q[num[3]].x,q[num[1]].y) + q[num[4]].x; 99 ms2 = mx(mx(q[num[2]].y ,q[num[3]].y)+q[num[1]].x,q[num[4]].y); 100 return 1; 101 } 102 int hehe4() 103 { 104 ms1 =0 ; 105 ms2 =0 ; 106 if(q[num[1]].x <= q[num[2]].x) 107 { 108 ms1 = q[num[2]].x + q[num[3]].x + q[num[4]].x; 109 ms2 = mx(mx(q[num[3]].y,q[num[4]].y),q[num[2]].y + q[num[1]].y); 110 return 1; 111 }else { 112 return 0; 113 } 114 } 115 int hehe5() 116 { 117 ms1 = 0 ; 118 ms2 = 0 ; 119 if(q[num[1]].y < q[num[3]].y) 120 { 121 return 0; 122 }else{ 123 if(q[num[1]].y - q[num[3]].y >= q[num[4]].y) 124 { 125 ms1 = mx(mx(q[num[2]].y,q[num[1]].x+q[num[4]].x),q[num[1]].x+q[num[3]].x); 126 ms2 = q[num[1]].y + q[num[2]].x; 127 }else 128 { 129 ms1 = mx(mx(q[num[2]].y+q[num[4]].x,q[num[1]].x+q[num[3]].x),q[num[1]].x +q[num[4]].x); 130 ms2 = mx(q[num[2]].x+q[num[1]].y,q[num[3]].y+q[num[4]].y); 131 } 132 return 1; 133 } 134 } 135 void solve(){ 136 137 for(int i = 0;i <= 15; i ++ ) 138 { 139 int k = i ; 140 for(int j = 1;j <= 4;j ++) 141 { 142 if(k % 2 == 0) 143 { 144 q[j] = p[j]; 145 } 146 else 147 { 148 q[j].x = p[j].y; 149 q[j].y = p[j].x; 150 } 151 k = k/2; 152 } 153 for(int i = 1;i <= 4;i ++) 154 num[i] = i ; 155 do{ 156 if(hehe1()) 157 ok(); 158 if(hehe2()) 159 ok(); 160 if(hehe3()) 161 ok(); 162 if(hehe4()) 163 ok(); 164 if(hehe5()) 165 ok(); 166 /* if(hehe6()) 167 ok();*/ 168 }while(next_permutation(num+1,num+5)); 169 } 170 171 172 } 173 174 int cmp(const void * a, const void *b) 175 { 176 return (*(node *)a).x - (*(node*)b).x; 177 } 178 int main() 179 { 180 // freopen("packrec.in","r",stdin); 181 // freopen("packrec.out","w",stdout); 182 FILE *p1, *p2; 183 p1 = fopen("packrec.in","r"); 184 p2 = fopen("packrec.out","w"); 185 for(int i =1;i <= 4;i ++) 186 { 187 fscanf(p1,"%d %d",&p[i].x,&p[i].y); 188 if(p[i].x > p[i].y) 189 { 190 int temp ; 191 temp = p[i].x; 192 p[i].x = p[i].y ; 193 p[i].y = temp; 194 } 195 } 196 solve(); 197 qsort(a+1,sum,sizeof(node),cmp); 198 fprintf(p2,"%d ",ans); 199 fprintf(p2,"%d %d ",a[1].x,a[1].y); 200 for(int i = 2;i <= sum;i ++) 201 { 202 if(a[i].x == a[i-1].x || a[i].y == a[i-1].y) 203 continue; 204 else fprintf(p2,"%d %d ",a[i].x,a[i].y); 205 if(i == sum) 206 fclose(p2); 207 } 208 fclose(p1); 209 //fclose(p2); 210 //printf("%d %d ",a[sum].x,a[sum].y); 211 return 0 ; 212 }