ch1 : Packing Rectangles


/ Published in: C++
Save to your folder(s)



Copy this code and paste it in your HTML
  1. /*
  2.   NAME : Nursoltan
  3.   PROB : packrec
  4.   LANG : C++
  5.   DATE : 29/06/11 15:14
  6. */
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cctype>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <ctime>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <map>
  18. #include <set>
  19. #include <stack>
  20. #include <utility>
  21. #include <queue>
  22.  
  23. using namespace std;
  24.  
  25. #define MAX 100
  26. #define INF INT_MAX
  27. #define eps (1e-9)
  28.  
  29. #define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
  30. #define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
  31. #define CLR(_x) memset((_x),0,sizeof(_x))
  32. #define SQR(_x) ((_x)*(_x))
  33. #define all(_x) _x.begin(),_x.end()
  34. #define sz(_x) sizeof(_x)
  35.  
  36. #define vc vector<int>
  37. #define pb push_back
  38. #define mp make_pair
  39. #define iss istringstream
  40. #define oss ostringstream
  41. #define h first
  42. #define l second
  43.  
  44. typedef long long ll;
  45. typedef pair <int,int> rect;
  46. int ABS(int _x){ return _x>0?_x:-_x; }
  47.  
  48. rect r,f;
  49. vector<rect> ans;
  50.  
  51. int max3(int a, int b, int c){
  52. return max(a,max(b,c));
  53. }
  54.  
  55. int max4(int a, int b, int c, int d){
  56. return max(max3(a,b,c),d);
  57. }
  58.  
  59. int layer1(rect a, rect b, rect c, rect d){
  60. int l,h;
  61. h=max4(a.h,b.h,c.h,d.h);
  62. l=a.l+b.l+c.l+d.l;
  63. r=mp(h,l);
  64. return h*l;
  65. }
  66.  
  67. int layer2(rect a, rect b, rect c, rect d){
  68. int l,h;
  69. h=max3(a.h,b.h,c.h)+d.h;
  70. l=max(a.l+b.l+c.l,d.l);
  71. r=mp(h,l);
  72. return h*l;
  73. }
  74.  
  75. int layer3(rect a, rect b, rect c, rect d){
  76. int l,h;
  77. h=max3(d.h,a.h+c.h,b.h+c.h);
  78. l=d.l+max(c.l,a.l+b.l);
  79. r=mp(h,l);
  80. return h*l;
  81. }
  82.  
  83. int layer4(rect a, rect b, rect c, rect d){
  84. int l,h;
  85. h=max3(a.h,c.h,b.h+d.h);
  86. l=a.l+c.l+max(b.l,d.l);
  87. r=mp(h,l);
  88. return h*l;
  89. }
  90.  
  91. int layer5(rect a, rect b, rect c, rect d){
  92. int l,h;
  93. h=max3(b.h,c.h,a.h+d.h);
  94. l=max(a.l,d.l)+b.l+c.l;
  95. r=mp(h,l);
  96. return h*l;
  97. }
  98.  
  99. int layer6(rect a, rect b, rect c, rect d){
  100. int l,h;
  101. h=max(a.h+b.h,c.h+d.h);
  102. l=max(a.l,b.l)+max(c.l,d.l);
  103. if(c.l>d.l && a.l<b.l && b.h<d.h) l-=min(c.l-d.l,b.l-a.l);
  104. r=mp(h,l);
  105. return h*l;
  106. }
  107.  
  108. int getMin(int a, int b){
  109. if(b<a){ f=r; }
  110. ans.pb(r);
  111. return min(a,b);
  112. }
  113.  
  114. int main(){
  115. freopen("packrec.in","r",stdin);
  116. freopen("packrec.out","w",stdout);
  117.  
  118. rect a[4];
  119. FOR(i,0,4) cin>>a[i].h>>a[i].l;
  120.  
  121. int ret=100000;
  122. int ord[4]={0,1,2,3};
  123. do{
  124. FOR(bit,0,(1<<4)){
  125. rect b[4]={a[0],a[1],a[2],a[3]};
  126. FOR(i,0,4) if(bit & (1<<i)) swap(b[i].h,b[i].l);
  127. ret=getMin(ret,layer1(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
  128. ret=getMin(ret,layer2(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
  129. ret=getMin(ret,layer3(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
  130. ret=getMin(ret,layer4(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
  131. ret=getMin(ret,layer6(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
  132. }
  133. }while(next_permutation(ord,ord+4));
  134.  
  135. vector<rect> realAns;
  136. FOR(i,0,ans.size()) if(ans[i].l*ans[i].h==ret){
  137. if(ans[i].l<ans[i].h) swap(ans[i].l,ans[i].h);
  138. realAns.pb(ans[i]);
  139. }
  140. sort(all(realAns));
  141.  
  142. cout<<ret<<endl;
  143. cout<<realAns[0].h<<" "<<realAns[0].l<<endl;
  144. FOR(i,1,realAns.size()){
  145. if(realAns[i].h==realAns[i-1].h &&
  146. realAns[i].l==realAns[i-1].l) continue;
  147. cout<<realAns[i].h<<" "<<realAns[i].l<<endl;
  148. }
  149.  
  150. //system("pause");
  151. return 0;
  152. }

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.