• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            superman

            聚精會神搞建設 一心一意謀發展
            posts - 190, comments - 17, trackbacks - 0, articles - 0
               :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            Section 1.4 - Packing Rectangles

            Posted on 2009-03-19 16:35 superman 閱讀(332) 評論(0)  編輯 收藏 引用 所屬分類: USACO
              1 #include <iostream>
              2 
              3 using namespace std;
              4 
              5 int max(int a, int b, int c)
              6 {
              7     return max(max(a, b), c);
              8 }
              9 
             10 int max(int a, int b, int c, int d)
             11 {
             12     return max(max(a, b, c), d);
             13 }
             14 
             15 struct Rectangle
             16 {
             17     int h;  //height
             18     int w;  //width
             19 }   rect[4];
             20 
             21 int ans = 65535;
             22 int ans_cnt = 0;
             23 int ans_w[24], ans_h[24];
             24 
             25 void updateAns(int tot_w, int tot_h)
             26 {
             27     if (tot_w * tot_h <= ans)
             28     {
             29         if (tot_w * tot_h < ans)
             30         {
             31             ans = tot_w * tot_h;
             32             ans_cnt = 0;
             33         }
             34         for (int i = 0; i < ans_cnt; i++)
             35             if (ans_w[i] == min(tot_w, tot_h) && ans_h[i] == max(tot_w, tot_h))
             36                 return;
             37         ans_w[ans_cnt] = min(tot_w, tot_h);
             38         ans_h[ans_cnt] = max(tot_w, tot_h);
             39         ans_cnt++;
             40     }
             41 }
             42 
             43 void calcArea(int x[], int i)
             44 {
             45     int h0 = rect[x[0]].h; int w0 = rect[x[0]].w;
             46     int h1 = rect[x[1]].h; int w1 = rect[x[1]].w;
             47     int h2 = rect[x[2]].h; int w2 = rect[x[2]].w;
             48     int h3 = rect[x[3]].h; int w3 = rect[x[3]].w;
             49     if ((i & 1== 1) swap(h0, w0);
             50     if ((i & 2== 2) swap(h1, w1);
             51     if ((i & 4== 4) swap(h2, w2);
             52     if ((i & 8== 8) swap(h3, w3);
             53 
             54     int tot_w, tot_h;
             55 
             56     //1
             57     tot_h = max(h0, h1, h2, h3);
             58     tot_w = w0 + w1 + w2 + w3;
             59     updateAns(tot_w, tot_h);
             60     //2
             61     tot_h = max(h0, h1, h2) + h3;
             62     tot_w = max(w0 + w1 + w2, w3);
             63     updateAns(tot_w, tot_h);
             64     //3
             65     tot_h = max(max(h0, h1) + h3, h2);
             66     tot_w = max(w0 + w1, w3) + w2;
             67     updateAns(tot_w, tot_h);
             68     //4
             69     tot_h = max(h0 + h1, h2, h3);
             70     tot_w = max(w0, w1) + w2 + w3;
             71     updateAns(tot_w, tot_h);
             72     //5
             73     tot_h = max(h0 + h1, h2 + h3);
             74     tot_w = max(w0 + w3, w1 + w2);
             75     if (h0 + h2 > tot_h && w0 + w2 > tot_w) return;
             76     if (h1 + h3 > tot_h && w1 + w3 > tot_w) return;
             77     updateAns(tot_w, tot_h);
             78 }
             79 
             80 void getPermutation(int x[], int p)
             81 {
             82     if (p >= 4)
             83     {
             84         for (int i = 0; i <= 15; i++)
             85             calcArea(x, i);
             86         return;
             87     }
             88     for (int i = p; i < 4; i++)
             89     {
             90         swap(x[i], x[p]);
             91         getPermutation(x, p + 1);
             92         swap(x[i], x[p]);
             93     }
             94 }
             95 
             96 int main()
             97 {
             98     freopen("packrec.in""r", stdin);
             99     freopen("packrec.out""w", stdout);
            100 
            101     for (int i = 0; i < 4; i++)
            102         cin >> rect[i].w >> rect[i].h;
            103 
            104     int x[4= { 0123 };  //the permutation of 4 rectangles
            105 
            106     getPermutation(x, 0);
            107 
            108     for (int i = 0; i < ans_cnt - 1; i++)
            109         for (int j = i + 1; j < ans_cnt; j++)
            110             if (ans_w[i] > ans_w[j])
            111             {
            112                 swap(ans_w[i], ans_w[j]);
            113                 swap(ans_h[i], ans_h[j]);
            114             }
            115 
            116     cout << ans << endl;
            117     for (int i = 0; i < ans_cnt; i++)
            118         cout << ans_w[i] << ' ' << ans_h[i] << endl;
            119 
            120     return 0;
            121 }
            122 
            久久精品午夜一区二区福利| 91久久成人免费| 久久综合九色综合网站| 国产韩国精品一区二区三区久久| 久久香蕉一级毛片| 四虎国产精品免费久久| 久久精品国产亚洲av麻豆小说| 国产午夜精品久久久久九九电影| 精品国产乱码久久久久软件| 日本久久久精品中文字幕| 狠狠色丁香久久婷婷综合图片 | 精品久久久久久综合日本| 久久精品国产色蜜蜜麻豆| 久久国产色AV免费观看| 伊人色综合九久久天天蜜桃| 一本大道加勒比久久综合| 亚洲精品午夜国产VA久久成人| 国产成人久久久精品二区三区 | 久久国产三级无码一区二区| 精品久久久久久无码专区不卡| 亚洲精品国产美女久久久| www久久久天天com| 精品久久国产一区二区三区香蕉 | 狠狠色噜噜色狠狠狠综合久久| 国内精品久久久久久99蜜桃| 伊人久久国产免费观看视频| 国产真实乱对白精彩久久| 麻豆精品久久久一区二区| 国产精品视频久久久| 亚洲精品乱码久久久久久久久久久久 | 久久综合给合综合久久| 国产高清美女一级a毛片久久w | 精品蜜臀久久久久99网站| 欧美久久久久久| 久久婷婷五月综合97色直播| 性做久久久久久久久| 人妻系列无码专区久久五月天| 色欲综合久久躁天天躁| 国产精品成人久久久| 久久久久亚洲精品天堂| 国产成人精品久久一区二区三区 |