Return to Snippet

Revision: 48358
at June 29, 2011 17:39 by Nursoltan


Initial Code
/*
  NAME : Nursoltan
  PROB : packrec
  LANG : C++
  DATE : 29/06/11 15:14
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <sstream>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <utility>
#include <queue>

using namespace std;

#define MAX 100
#define INF INT_MAX
#define eps (1e-9)

#define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
#define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
#define CLR(_x) memset((_x),0,sizeof(_x))
#define SQR(_x) ((_x)*(_x))
#define all(_x) _x.begin(),_x.end()
#define sz(_x) sizeof(_x)

#define vc vector<int>
#define pb push_back
#define mp make_pair
#define iss istringstream
#define oss ostringstream
#define h first
#define l second

typedef long long ll;
typedef pair <int,int> rect;
int ABS(int _x){ return _x>0?_x:-_x; }

rect r,f;
vector<rect> ans;

int max3(int a, int b, int c){
    return max(a,max(b,c));
}

int max4(int a, int b, int c, int d){
    return max(max3(a,b,c),d);
}

int layer1(rect a, rect b, rect c, rect d){
    int l,h;
    h=max4(a.h,b.h,c.h,d.h);
    l=a.l+b.l+c.l+d.l;
    r=mp(h,l);
    return h*l;
}

int layer2(rect a, rect b, rect c, rect d){
    int l,h;
    h=max3(a.h,b.h,c.h)+d.h;
    l=max(a.l+b.l+c.l,d.l);
    r=mp(h,l);
    return h*l;
}

int layer3(rect a, rect b, rect c, rect d){
    int l,h;
    h=max3(d.h,a.h+c.h,b.h+c.h);
    l=d.l+max(c.l,a.l+b.l);
    r=mp(h,l);
    return h*l;
}

int layer4(rect a, rect b, rect c, rect d){
    int l,h;
    h=max3(a.h,c.h,b.h+d.h);
    l=a.l+c.l+max(b.l,d.l);
    r=mp(h,l);
    return h*l;
}

int layer5(rect a, rect b, rect c, rect d){
    int l,h;
    h=max3(b.h,c.h,a.h+d.h);
    l=max(a.l,d.l)+b.l+c.l;
    r=mp(h,l);
    return h*l;
}

int layer6(rect a, rect b, rect c, rect d){
    int l,h;
    h=max(a.h+b.h,c.h+d.h);
    l=max(a.l,b.l)+max(c.l,d.l);
    if(c.l>d.l && a.l<b.l && b.h<d.h) l-=min(c.l-d.l,b.l-a.l);
    r=mp(h,l);
    return h*l;
}

int getMin(int a, int b){
    if(b<a){ f=r; }
    ans.pb(r);
    return min(a,b);
}

int main(){
    freopen("packrec.in","r",stdin);
    freopen("packrec.out","w",stdout);
    
    rect a[4];
    FOR(i,0,4) cin>>a[i].h>>a[i].l; 
    
    int ret=100000;
    int ord[4]={0,1,2,3};
    do{
        FOR(bit,0,(1<<4)){
          rect b[4]={a[0],a[1],a[2],a[3]};
          FOR(i,0,4) if(bit & (1<<i)) swap(b[i].h,b[i].l);
          ret=getMin(ret,layer1(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
          ret=getMin(ret,layer2(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
          ret=getMin(ret,layer3(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
          ret=getMin(ret,layer4(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
          ret=getMin(ret,layer6(b[ord[0]],b[ord[1]],b[ord[2]],b[ord[3]]));
        }
      }while(next_permutation(ord,ord+4));
    
    vector<rect> realAns;
    FOR(i,0,ans.size()) if(ans[i].l*ans[i].h==ret){
                          if(ans[i].l<ans[i].h) swap(ans[i].l,ans[i].h);                        
                          realAns.pb(ans[i]);
                        }
    sort(all(realAns));
    
    cout<<ret<<endl;
    cout<<realAns[0].h<<" "<<realAns[0].l<<endl;
    FOR(i,1,realAns.size()){
      if(realAns[i].h==realAns[i-1].h && 
         realAns[i].l==realAns[i-1].l) continue;
      cout<<realAns[i].h<<" "<<realAns[i].l<<endl;
    }
    
    //system("pause");
    return 0;
}

Initial URL

                                

Initial Description

                                

Initial Title
ch1 : Packing Rectangles

Initial Tags

                                

Initial Language
C++