Home > Old Blog Posts > USACO 1.4.1 Packing Rectangles

USACO 1.4.1 Packing Rectangles


算是第一章最恶心的一道题了

这道题考验的根本就不是OI,而是耐心..

特别是第6个图,情况之复杂,简直令人抓狂……

设w1,w2,w3,w4表示4个方块的横长,h1,h2,h3,h4表示4个方块的纵长。w,h表示最小。
1:w=w1+w2+w3+w4;h=max(h1,h2,h3,h4)
2:w=max(w1+w2+w3,w4);h=max(h1,h2,h3)+h4
3:w=max(w1+w2,w3)+w4;h=max(h1+h3,h2+h3,h4)
4:w=w1+w2+max(w3,w4);h=max(h1,h3+h4,h2)
5:h=max(h1+h3,h2+h4)
对于w,我们细分为如下四种形式:
packrecx
(1):h3>=h2+h4;w=max(w1,w3+w2,w3+w4)
(2):h3>h4 and h3<h2+h4;w=max(w1+w2,w2+w3,w3+w4)
(3):h4>h3 and h4<h1+h3;w=max(w1+w2,w1+w4,w3+w4)
(4):h4>=h1+h3;w=max(w2,w1+w4,w3+w4)
*:h3=h4(图中没画);w=max(w1+w2,w3+w4)

代码:

/*
ID: dementr1
PROG: packrec
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“packrec.in”);
ofstream fout(“packrec.out”);
struct rect
{
int a,b;
};
struct save
{
short a,b,s;
} list[2000];
int a[4][2],number;
void init()
{
int i;
for(i=0;i<4;i++)
fin>>a[i][0]>>a[i][1];
number=0;
}
void swap(save *a, save *b)
{
save x=*a;
*a=*b;
*b=x;
}
void makeup()
{
int i;
for(i=0;i<number;i++)
{
if(list[i].b<list[i].a)
{
int t=list[i].a;
list[i].a=list[i].b;
list[i].b=t;
}
}
}
bool comp(save a, save b)
{
if(a.s<b.s) return true;
if(a.s>b.s) return false;
if(a.a<b.a) return true;
return false;
}
int partition(save A[],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
if(comp(A[j],A[right]))
{
i++;
swap(&A[i],&A[j]);
}
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(save A[], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
void try1(rect s[])
{
save ans;
int tmp;
ans.a=s[0].a+s[1].a+s[2].a+s[3].a;
tmp=s[0].b;
if(s[1].b>tmp) tmp=s[1].b;
if(s[2].b>tmp) tmp=s[2].b;
if(s[3].b>tmp) tmp=s[3].b;
ans.b=tmp;
ans.s=ans.a*ans.b;
list[number++]=ans;
}
void try2(rect s[])
{
save ans;
int tmpa=s[0].a+s[1].a+s[2].a;
ans.a=tmpa;
if(s[3].a>ans.a) ans.a=s[3].a;
int tmpb=s[0].b;
if(s[1].b>tmpb) tmpb=s[1].b;
if(s[2].b>tmpb) tmpb=s[2].b;
ans.b=tmpb+s[3].b;
ans.s=ans.a*ans.b;
list[number++]=ans;
}
void try3(rect s[])
{
int i;
save ans;
int tmpa=s[0].a+s[1].a;
if(s[2].a>tmpa) tmpa=s[2].a;
ans.a=tmpa+s[3].a;
int tmpb=s[0].b;
if(s[1].b>tmpb) tmpb=s[1].b;
tmpb+=s[2].b;
if(s[3].b>tmpb) tmpb=s[3].b;
ans.b=tmpb;
ans.s=ans.a*ans.b;
list[number++]=ans;
if(ans.s==21)
}
void try4(rect s[])
{
save ans;
int tmpa=s[0].a+s[3].a;
if(s[1].a>s[2].a) tmpa+=s[1].a;
else tmpa+=s[2].a;
ans.a=tmpa;
int tmpb=s[1].b+s[2].b;
if(s[0].b>tmpb) tmpb=s[0].b;
if(s[3].b>tmpb) tmpb=s[3].b;
ans.b=tmpb;
ans.s=ans.a*ans.b;
list[number++]=ans;
}
void try5(rect s[])
{
save ans;
ans.a = max(s[0].a+s[2].a, s[1].a+s[3].a);
ans.b = s[0].b + s[1].b;
if(s[0].a < s[1].a)
ans.b = max(ans.b, s[2].b+s[1].b);
if(s[0].a+s[2].a > s[1].a)
ans.b = max(ans.b, s[2].b+s[3].b);
if(s[1].a < s[0].a)
ans.b = max(ans.b, s[0].b+s[3].b);
ans.b = max(ans.b, s[2].b);
ans.b = max(ans.b, s[3].b);
ans.s=ans.a*ans.b;
list[number++]=ans;
}
void work()
{
rect s[4];
int b[4],c[4],i;
for(c[0]=0;c[0]<4;c[0]++)
for(c[1]=0;c[1]<4;c[1]++)
if(c[1]!=c[0])
for(c[2]=0;c[2]<4;c[2]++)
if(c[2]!=c[1] && c[2]!=c[0])
for(c[3]=0;c[3]<4;c[3]++)
if(c[3]!=c[2] && c[3]!=c[1] && c[3]!=c[0])
for(b[0]=0;b[0]<=1;b[0]++)
for(b[1]=0;b[1]<=1;b[1]++)
for(b[2]=0;b[2]<=1;b[2]++)
for(b[3]=0;b[3]<=1;b[3]++)
{
for(i=0;i<4;i++)
{
if(b[i]==0)
{
s[c[i]].a=a[i][0];
s[c[i]].b=a[i][1];
}
else
{
s[c[i]].a=a[i][1];
s[c[i]].b=a[i][0];
}
}
try1(s);
try2(s);
try3(s);
try4(s);
try5(s);
}
}
int main()
{
init();
work();
makeup();
quicksort(list,0,number-1);
fout<<list[0].s<<endl;
int i=0;
while(list[i].s==list[0].s)
{
if(i==0||!(list[i].a==list[i-1].a&&list[i].b==list[i-1].b&&list[i].s==list[i-1].s))
{
if(list[i].a>list[i].b) fout<<list[i].b<<” “<<list[i].a<<endl;
else fout<<list[i].a<<” “<<list[i].b<<endl;
}
i++;
}
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: