usaco_packrec.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: packrec
LANG: C++
*/ 


#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream in("packrec.in");
ofstream out("packrec.out");

#define MAX 0x7fffffff

typedef struct 
{
 int x;
 int y;
}rec;

int min_area = MAX;

rec soln[1000];
int ps = 0;
rec r[4];

rec t[4];

rec zero={0,0};

int v[4];

inline void make(rec p)
{
 if(p.x>p.y)
 {
  p.x = p.x ^ p.y;
  p.y = p.x ^ p.y;
  p.x = p.x ^ p.y;  
 }
 if(min_area > p.x*p.y)
 {
  min_area = p.x*p.y;
  ps = 0;
  soln[ps++] = p;
 }
 else if(min_area == p.x * p.y)
 {
  soln[ps++] = p;
 }
}
void search()
{
 int i;
 for(int a=0;a<4;a++)
 for(int b=0;b<4;b++)
 for(int c=0;c<4;c++)
 for(int d=0;d<4;d++)
 {
  if(a != b)
  if(a != c)
  if(a != d)
  if(b != c)
  if(b != d)
  if(c != d)
  {

   for(v[0]=0;v[0]<2;v[0]++)
    for(v[1]=0;v[1]<2;v[1]++)
     for(v[2]=0;v[2]<2;v[2]++)
      for(v[3]=0;v[3]<2;v[3]++)
      {
       t[0] = r[a];
       t[1] = r[b];
       t[2] = r[c];
       t[3] = r[d];

       for(i=0;i<4;i++)
        if(v[i] == 1)
        {
         t[i].x = t[i].x ^ t[i].y;
         t[i].y = t[i].x ^ t[i].y;
         t[i].x = t[i].x ^ t[i].y;
        }

       //1
       rec p = zero;
       p.x = max(t[0].x,max(t[1].x,max(t[2].x,t[3].x)));
       p.y = t[0].y + t[1].y + t[2].y + t[3].y;
       make(p);

       if(p.x == 10 && p.y == 8)
        p=p;

       //2
       p = zero;
       p.x = max(t[0].x,max(t[1].x,t[2].x)) + t[3].y;
       p.y = max(t[0].y+t[1].y+t[2].y,t[3].x);
       make(p);
       if(p.x == 10 && p.y == 8)
        p=p;
       //3
       p = zero;
       p.x = max(max(t[0].x,t[1].x)+t[2].x,t[3].x);
       p.y = max(t[0].y+t[1].y,t[2].y)+t[3].y;
       make(p);
       if(p.x == 10 && p.y == 8)
        p=p;
       //4
       p = zero;
       p.x = max(t[0].x,max(t[1].x+t[2].x,t[3].x));
       p.y = t[0].y + max(t[1].y,t[2].y) + t[3].y ;
       make(p);
       if(p.x == 10 && p.y == 8)
        p=p;
       //5
       //同上

       //6

       if(t[0].y>t[1].y)
        continue;

       if(t[3].x > t[0].x+t[1].x)
        continue;
       if(t[3].x<t[1].x)
        continue;

       p = zero;
       p.x = max(t[0].x+t[1].x,t[2].y+t[3].x);
       p.y = max(t[1].y+t[3].y,t[0].y+t[2].x);
       make(p);
       if(p.x == 6 && p.y == 6)
        p=p;
      }
  }
 }
}

bool comp(rec a,rec b)
{
 if(a.x<b.x)
  return 1;
 else if(a.x == b.x && a.y<b.y)
  return 1;
 else
  return 0;
}

bool comp2(rec a,rec b)
{
 return a.x==b.x && a.y==b.y;
}

int main()
{
 for(int i=0;i<4;i++)
 {
  in>>r[i].x>>r[i].y;
 }
 search();
 sort(&soln[0],&soln[ps],comp);


 rec *t = unique(&soln[0],&soln[ps],comp2);

 

 out<<min_area<<endl;
 for(rec *i=&soln[0];i!=t;i++)
  out<<(*i).x<<" "<<(*i).y<<endl;
 return 0;
}