Guest User

Untitled

a guest
Jun 19th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.51 KB | None | 0 0
  1. /*
  2. ID: IdolfHatler
  3. PROG: packrec
  4. LANG: C++
  5. */
  6. #include <iostream>
  7. #include <fstream>
  8. #include <string>
  9. #include <string.h>
  10. #include <algorithm>
  11.  
  12. #define min3(a,b,c) min(min(a,b), c)
  13. #define min4(a,b,c,d) min(min3(a, b, c), d)
  14. #define max3(a,b,c) max(max(a,b), c)
  15. #define max4(a,b,c,d) max(max3(a, b, c), d)
  16. #define CUR layouts[perm][flip]
  17.  
  18. using namespace std;
  19.  
  20. struct rec {
  21. int x;
  22. int y;
  23. const bool operator<(const rec &other) const {
  24. return x < other.x || (x == other.x && y < other.y);
  25. }
  26. };
  27.  
  28. struct layout {
  29. int size;
  30. int x;
  31. int y;
  32. const bool operator<(const layout &other) const {
  33. return size < other.size || (size == other.size && x < other.x);
  34. }
  35. };
  36.  
  37. int perm_two[24][4] = {
  38. {0,1,2,3}, {0,1,3,2}, {0,2,1,3}, {0,2,3,1}, {0,3,1,2}, {0,3,2,1},
  39. {1,0,2,3}, {1,0,3,2}, {1,2,0,3}, {1,2,3,0}, {1,3,0,2}, {1,3,2,0},
  40. {2,0,1,3}, {2,0,3,1}, {2,1,0,3}, {2,1,3,0}, {2,3,0,1}, {2,3,1,0},
  41. {3,0,1,2}, {3,0,2,1}, {3,1,0,2}, {3,1,2,0}, {3,2,0,1}, {3,2,1,0}
  42. };
  43.  
  44.  
  45. int main() {
  46. ofstream fout ("packrec.out");
  47. ifstream fin ("packrec.in");
  48.  
  49. rec rectangles[4];
  50. layout layouts[24][16][5];
  51.  
  52. for(int n = 0; n < 4; n++) {
  53. int x, y;
  54. fin >> x >> y;
  55.  
  56. rectangles[n].x = x;
  57. rectangles[n].y = y;
  58. }
  59.  
  60. memset(layouts, 0, sizeof(layouts));
  61.  
  62. for(int perm = 0; perm < 24; perm++) {
  63. for(int flip = 0; flip < 16; flip++) {
  64. rec a, b, c, d;
  65. memcpy(&a, &rectangles[perm_two[perm][0]], sizeof(a));
  66. memcpy(&b, &rectangles[perm_two[perm][1]], sizeof(b));
  67. memcpy(&c, &rectangles[perm_two[perm][2]], sizeof(c));
  68. memcpy(&d, &rectangles[perm_two[perm][3]], sizeof(d));
  69.  
  70. int tmp;
  71. if(flip & 1) {
  72. tmp = a.x;
  73. a.x = a.y;
  74. a.y = tmp;
  75. }
  76. if(flip & 2) {
  77. tmp = b.x;
  78. b.x = b.y;
  79. b.y = tmp;
  80. }
  81. if(flip & 4) {
  82. tmp = c.x;
  83. c.x = c.y;
  84. c.y = tmp;
  85. }
  86. if(flip & 8) {
  87. tmp = d.x;
  88. d.x = d.y;
  89. d.y = tmp;
  90. }
  91.  
  92.  
  93. // cout << ((flip&8) > 0);
  94. // cout << ((flip&4) > 0);
  95. // cout << ((flip&2) > 0);
  96. // cout << ((flip&1) > 0);
  97. // cout << perm_two[perm][0];
  98. // cout << perm_two[perm][1];
  99. // cout << perm_two[perm][2];
  100. // cout << perm_two[perm][3];
  101. // cout << " a(" << a.x << "," << a.y << ")";
  102. // cout << " b(" << b.x << "," << b.y << ")";
  103. // cout << " c(" << c.x << "," << c.y << ")";
  104. // cout << " d(" << d.x << "," << d.y << ")";
  105. // cout << endl;
  106.  
  107. // Layout 0
  108. CUR[0].x = a.x + b.x + c.x + d.x;
  109. CUR[0].y = max4(a.y, b.y, c.y, d.y);
  110. // cout << "0: ";
  111. // cout << CUR[0].x << " ";
  112. // cout << CUR[0].y << " ";
  113. // cout << endl;
  114.  
  115. // Layout 1
  116. CUR[1].x = max(a.y, b.x+c.x+d.x);
  117. CUR[1].y = max3(b.y, c.y, d.y)+a.x;
  118. // cout << "1: ";
  119. // cout << CUR[1].x << " ";
  120. // cout << CUR[1].y << " ";
  121. // cout << endl;
  122.  
  123. // Layout 2
  124. CUR[2].x = max(a.y, b.x+c.x) + d.x;
  125. CUR[2].y = max(a.x + max(b.y, c.y), d.y);
  126. // cout << "2: ";
  127. // cout << CUR[2].x << " ";
  128. // cout << CUR[2].y << " ";
  129. // cout << endl;
  130.  
  131. // Layout 3
  132. CUR[3].x = a.x + max(b.x, c.x) + d.x;
  133. CUR[3].y = max3(a.y, b.y+c.y, d.y);
  134. // cout << "3: ";
  135. // cout << CUR[3].x << " ";
  136. // cout << CUR[3].y << " ";
  137. // cout << endl;
  138.  
  139. // Layout 4
  140. if(a.x > b.x || b.y > c.y) {
  141. CUR[4].x = 999;
  142. CUR[4].y = 999;
  143. } else {
  144. CUR[4].x = max(a.x+d.y, b.x+c.x);
  145. CUR[4].y = max(a.y+b.y, c.y+d.x);
  146. }
  147.  
  148. // cout << "4: ";
  149. // cout << CUR[4].x << " ";
  150. // cout << CUR[4].y << " ";
  151. // cout << endl;
  152. // cout << endl;
  153.  
  154. for(int n = 0; n < 5; n++) {
  155. if(CUR[n].x > CUR[n].y) {
  156. tmp = CUR[n].x;
  157. CUR[n].x = CUR[n].y;
  158. CUR[n].y = tmp;
  159. }
  160. CUR[n].size = CUR[n].x * CUR[n].y;
  161. if(CUR[n].size <= 40) {
  162. // cout << (flip&1 > 0) << (flip&2 > 0) << (flip&4 > 0) << (flip&8 > 0);
  163. // cout << perm_two[perm][0];
  164. // cout << perm_two[perm][1];
  165. // cout << perm_two[perm][2];
  166. // cout << perm_two[perm][3];
  167. // cout << " " << n << " "<< CUR[n].x << " " << CUR[n].y << " " << CUR[n].size;
  168. // cout << endl;
  169. }
  170. }
  171.  
  172. }
  173. }
  174.  
  175. sort(&layouts[0][0][0], &layouts[24][0][0]);
  176.  
  177. int size = layouts[0][0][0].size;
  178. int cur_x = -1;
  179.  
  180. for(int n = 0; n < 24*16*5; n++) {
  181. // cout << layouts[0][0][n].size << " " << layouts[0][0][n].x << " " << layouts[0][0][n].y << endl;
  182. }
  183.  
  184. fout << size << endl;
  185.  
  186. for(int n = 0; n < 24*16*5 && layouts[0][0][n].size == size; n++) {
  187. if(layouts[0][0][n].x > cur_x) {
  188. cur_x = layouts[0][0][n].x;
  189. fout << layouts[0][0][n].x << " " << layouts[0][0][n].y << endl;
  190. }
  191. }
  192.  
  193. return 0;
  194. }
Add Comment
Please, Sign In to add comment