1.4/packrec.java

   1 /*
   2 ID: raincro1
   3 LANG: JAVA
   4 TASK: packrec
   5 */
   6 import java.io.*;
   7 import java.util.*;
   8
   9 class packrec {
  10     static class IO {
  11         public BufferedReader   f;
  12         StringTokenizer         st;
  13         public PrintWriter      out;
  14
  15         public String           line;
  16
  17         public IO () throws IOException {
  18             f = new BufferedReader(new FileReader(name + ".in"));
  19             out = new PrintWriter(new BufferedWriter(new FileWriter(name + ".out")));
  20         }
  21
  22         public String nextLine() throws IOException {
  23             line = f.readLine();
  24             st = null;
  25             return line;
  26         }
  27
  28         public int nextIntLine() throws IOException {
  29             return Integer.parseInt(nextLine());
  30         }
  31
  32         public void tokenize() {
  33             st = new StringTokenizer(line);
  34         }
  35
  36         public String nextToken() {
  37             if(st == null) tokenize();
  38             return st.nextToken();
  39         }
  40
  41         public int nextIntToken() {
  42             return Integer.parseInt(nextToken());
  43         }
  44
  45         public void close() {
  46             out.close();                                  // close the output file
  47             System.exit(0);                               // don't omit this!
  48         }
  49     }
  50
  51     static boolean          debug = false;
  52     static String           name  = "packrec";
  53
  54     static IO               io;
  55
  56     //////////////////////////////////////////
  57
  58     static int                          min_area;
  59     static TreeMap<Integer, Integer>    min_map;
  60
  61     static class Rect {
  62         int     x, y;
  63
  64         public Rect (int x, int y) {
  65             this.x = x;
  66             this.y = y;
  67         }
  68
  69         Rect growRight(Rect peer){
  70             return new Rect(this.x + peer.x, this.y > peer.y ? this.y : peer.y);
  71         }
  72
  73         Rect growDown(Rect peer) {
  74             return new Rect(this.x > peer.x ? this.x : peer.x, this.y + peer.y);
  75         }
  76
  77         boolean isSmall() {
  78             return x * y < min_area;        // search tree pruning
  79         }
  80
  81         void checkResult() {
  82             int area = x * y;
  83
  84             if(min_area > area) {
  85                 min_area = area;
  86                 min_map.clear();
  87             }
  88
  89             if(min_area == area) {
  90                 if(x <= y)  min_map.put(x, y);
  91                 else        min_map.put(y, x);
  92             }
  93         }
  94     }
  95
  96     static void checkLast(Rect r1, Rect r2, Rect r3, Rect r4){
  97         // check layout 6
  98
  99         //
 100         //   1  4
 101         //   2  3
 102         //
 103
 104         int mx = r1.x;
 105         if(mx < r2.x) mx = r2.x;
 106
 107         int b;
 108
 109         if(r2.y > r3.y){
 110             if(r2.y >= r3.y + r4.y){
 111                 return;         // this is equivalent to layout 3
 112             }
 113
 114             mx += r4.x;
 115
 116             b = r2.x + r3.x;
 117         }else{
 118             if(r1.y + r2.y <= r3.y){
 119                 return;         // this is equivalent to layout 3
 120             }
 121
 122             mx += r3.x;
 123
 124             b = r1.x + r4.x;
 125         }
 126
 127         if(mx < b) mx = b;
 128
 129         int my = r1.y + r2.y;
 130         int c = r3.y + r4.y;
 131         if(my < c) my = c;
 132
 133         (new Rect(mx, my)).checkResult();
 134     }
 135
 136     static void checkOther(Rect r1, Rect r2, Rect r3, Rect r4){
 137         final Rect block = r1.growRight(r2);
 138
 139         if(block.isSmall()){
 140             block.growDown(r3).growRight(r4).checkResult();     // layout 3
 141             block.growRight(r3.growDown(r4)).checkResult();     // layout 5
 142         }
 143
 144         checkLast(r1, r2, r3, r4);
 145         checkLast(r2, r1, r3, r4);
 146     }
 147
 148     static void iterate3rd(Rect r1, Rect r2, Rect r3, Rect r4){
 149         final Rect block = r1.growRight(r2).growRight(r3);
 150
 151         if(block.isSmall()){
 152             block.growRight(r4).checkResult();                  // layout 1
 153             block.growDown(r4).checkResult();                   // layout 2
 154         }
 155
 156         // iterate 3rd parameter
 157         checkOther(r1, r2, r3, r4);
 158         checkOther(r1, r3, r2, r4);
 159         checkOther(r2, r3, r1, r4);
 160     }
 161
 162     static void iterate4th(
 163         int x1, int y1, int x2, int y2,
 164         int x3, int y3, int x4, int y4)
 165     {
 166         Rect    r1 = new Rect(x1, y1);
 167         Rect    r2 = new Rect(x2, y2);
 168         Rect    r3 = new Rect(x3, y3);
 169         Rect    r4 = new Rect(x4, y4);
 170
 171         // iterate 4th parameter
 172         iterate3rd(r1, r2, r3, r4);
 173         iterate3rd(r1, r2, r4, r3);     // NOTE: checkOther performs the same blockcheck twice, but we dont care for now
 174         iterate3rd(r1, r3, r4, r2);
 175         iterate3rd(r2, r3, r4, r1);
 176     }
 177
 178     public static void main (String [] args) throws IOException {
 179         io = new IO();
 180
 181         io.nextLine();
 182         final int x1 = io.nextIntToken();
 183         final int y1 = io.nextIntToken();
 184
 185         io.nextLine();
 186         final int x2 = io.nextIntToken();
 187         final int y2 = io.nextIntToken();
 188
 189         io.nextLine();
 190         final int x3 = io.nextIntToken();
 191         final int y3 = io.nextIntToken();
 192
 193         io.nextLine();
 194         final int x4 = io.nextIntToken();
 195         final int y4 = io.nextIntToken();
 196
 197         min_area = (x1 + x2 + x3 + x4) * (y1 + y2 + y3 + y4) * 2;
 198
 199         min_map = new TreeMap<Integer, Integer> ();
 200
 201         // iterate all transpositions
 202         iterate4th(x1, y1, x2, y2, x3, y3, x4, y4);
 203         iterate4th(x1, y1, x2, y2, x3, y3, y4, x4);
 204
 205         iterate4th(x1, y1, x2, y2, y3, x3, x4, y4);
 206         iterate4th(x1, y1, x2, y2, y3, x3, y4, x4);
 207
 208
 209         iterate4th(x1, y1, y2, x2, x3, y3, x4, y4);
 210         iterate4th(x1, y1, y2, x2, x3, y3, y4, x4);
 211
 212         iterate4th(x1, y1, y2, x2, y3, x3, x4, y4);
 213         iterate4th(x1, y1, y2, x2, y3, x3, y4, x4);
 214
 215
 216         iterate4th(y1, x1, x2, y2, x3, y3, x4, y4);
 217         iterate4th(y1, x1, x2, y2, x3, y3, y4, x4);
 218
 219         iterate4th(y1, x1, x2, y2, y3, x3, x4, y4);
 220         iterate4th(y1, x1, x2, y2, y3, x3, y4, x4);
 221
 222
 223         iterate4th(y1, x1, y2, x2, x3, y3, x4, y4);
 224         iterate4th(y1, x1, y2, x2, x3, y3, y4, x4);
 225
 226         iterate4th(y1, x1, y2, x2, y3, x3, x4, y4);
 227         iterate4th(y1, x1, y2, x2, y3, x3, y4, x4);
 228
 229
 230         io.out.println(min_area);
 231
 232         Map.Entry<Integer, Integer>     entry;
 233
 234         while((entry = min_map.pollFirstEntry()) != null) {
 235             io.out.printf("%d %d\n", entry.getKey(), entry.getValue());
 236         }
 237
 238         io.close();
 239     }
 240 }
 241
 242