📄 code.txt
字号:
#include<stdio.h>
#include"stdlib.h"
#define LEN sizeof(struct DE)
struct BC
{
long long x,y;
};
struct DE
{
long long x[2],y[2];
struct DE *next;
};
struct K
{
long long x[2],y[2];
int k;
};
void paixu(struct BC a[],int n,int d[]) //该方法是对举行面积进行排序
{
int i,j;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
if(a[i].x*a[i].y<a[j].x*a[j].y)
{
a[i].x=a[i].x+a[j].x;
a[j].x=a[i].x-a[j].x;
a[i].x=a[i].x-a[j].x;
a[i].y=a[i].y+a[j].y;
a[j].y=a[i].y-a[j].y;
a[i].y=a[i].y-a[j].y;
d[i]=d[i]+d[j];
d[j]=d[i]-d[j];
d[i]=d[i]-d[j];
}
}
void meiju(struct BC a[],int n,int d[],long long b,long long c) //矩形个数小的时候用的枚举方法
{
int i,j,k=1,p,m,l,t,q,h=0,r=0,s,u=0,f[2000];
long long s1=0,s2=0,powerN;
struct K g[10]={0},o[10]={0};
struct BC e[2000];
struct DE *e1,*e2,*head;
powerN=1<<n;
for(i=0;i<powerN;i++)
{
k=1;
h=0;
m=0;
t=i+1;
s1=0;
head=(struct DE*)malloc(LEN);
head->x[0]=0; head->y[0]=0;
head->x[1]=b;head->y[1]=c;//记下原点的坐标
head->next=NULL;
for(j=0;j<n;j++)
{
if(t%2==1)
{
e[m]=a[j];
f[m]=d[j];
t=t/2;
m++;
}
else
t=t/2;
if(t==0)
break;
}
for(q=0;q<k;q++)
{
p=0;
for(l=0;l<m;l++)
{
if(e[l].x==0 ||e[l].y==0)
continue;
else
{
if(head->x[1]-head->x[0]<head->y[1]-head->y[0])
{
e[l].x=e[l].y+e[l].x;
e[l].y=e[l].x-e[l].y;
e[l].x=e[l].x-e[l].y;
} //如果那个要剪的长方形横左边的差小于纵坐标，就交换那个给定的长方形的长跟宽
if(head->x[1]-head->x[0]>e[l].x && head->y[1]-head->y[0]>e[l].y)
{
g[h].x[0]=head->x[0];g[h].y[0]=head->y[0];
g[h].x[1]=head->x[0]+e[l].x;g[h].y[1]=head->y[0]+e[l].y;
g[h].k=f[l];
s1=s1+(g[h].x[1]-g[h].x[0])*(g[h].y[1]-g[h].y[0]);
h++;
if(((head->x[1]-head->x[0]-e[l].x)*e[l].y)>(head->x[1]-head->x[0])*(head->y[1]-head->y[0]-e[l].y))
{
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0]+e[l].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[0]+e[l].y;
e1=(struct DE*)malloc(LEN);
e1->next=head;
head=e1;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+e[l].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
free(e2);
}
else
{
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+e[l].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
e1=(struct DE*)malloc(LEN);
e1->next=head;
head=e1;
head->x[0]=e2->x[0]+e[l].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[0]+e[l].y;
free(e2);
}//把纸面积最小的放在最前
e[l].x=0;e[l].y=0;
p=1;
k=k+2;
break;
}//如果被剪的矩形的长宽都小于那张纸的
else
if(head->x[1]-head->x[0]==e[l].x && head->y[1]-head->y[0]>e[l].y)
{
g[h].x[0]=head->x[0];g[h].y[0]=head->y[0];
g[h].x[1]=head->x[0]+e[l].x;g[h].y[1]=head->y[0]+e[l].y;
g[h].k=f[l];
s1=s1+(g[h].x[1]-g[h].x[0])*(g[h].y[1]-g[h].y[0]);
h++;
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+e[l].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
free(e2);
e[l].x=0;e[l].y=0;//把纸面积最小的放在最前
k=k+1;
p=1;
break;
}//如果被剪的矩形的宽小于那张纸的，长等于那张纸
else
if(head->x[1]-head->x[0]>e[l].x && head->y[1]-head->y[0]==e[l].y)
{
g[h].x[0]=head->x[0];g[h].y[0]=head->y[0];
g[h].x[1]=head->x[0]+e[l].x;g[h].y[1]=head->y[0]+e[l].y;
g[h].k=f[l];
s1=s1+(g[h].x[1]-g[h].x[0])*(g[h].y[1]-g[h].y[0]);
h++;
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0]+e[l].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
e[l].x=0;e[l].y=0;
free(e2);
k=k+1;
p=1;
break;
}//如果被剪的矩形的长小于那张纸的，宽等于那张纸
else
if(head->x[1]-head->x[0]==e[l].x && head->y[1]-head->y[0]==e[l].y)
{
g[h].x[0]=head->x[0];g[h].y[0]=head->y[0];
g[h].x[1]=head->x[0]+e[l].x;g[h].y[1]=head->y[0]+e[l].y;
g[h].k=f[l];
s1=s1+(g[h].x[1]-g[h].x[0])*(g[h].y[1]-g[h].y[0]);
h++;
e2=head;
head=head->next;
free(e2);
e[l].x=0;e[l].y=0;
k=k;
p=1;
break;
}//如果被剪的矩形的长宽都等于那张纸的
if(e[l].x<e[l].y)
{
e[l].x=e[l].y+e[l].x;
e[l].y=e[l].x-e[l].y;
e[l].x=e[l].x-e[l].y;
}//恢复为原来长在前面，宽在后面
}
}
if(p==0)
{ e2=head;
head=e2->next;
free(e2);
}
}
if(s1>s2)
{ for(s=0;s<h;s++)
{
o[s]=g[s];
}
u=h;s2=s1;
}
}
for(i=0;i<u;i++)
{
printf("%d %I64d %I64d %I64d %I64d\n",o[i].k,o[i].x[0],o[i].y[0],o[i].x[1],o[i].y[1]);
}
}
void tanxin(struct BC a[],int n,int d[],long long b,long long c)//当矩形数较多时用贪心
{
int i,j,k,p;
struct DE *e1,*e2,*head;
k=1;
p=0;
head=(struct DE*)malloc(LEN);
head->x[0]=0; head->y[0]=0;
head->x[1]=b;head->y[1]=c;//记下原点的坐标
head->next=NULL;
for(i=0;i<k;i++)
{
for(j=0;j<n;j++)
{ p=0;
if(a[j].x==0 ||a[j].y==0)
continue;
else
{
if(head->x[1]-head->x[0]<head->y[1]-head->y[0])
{
a[j].x=a[j].y+a[j].x;
a[j].y=a[j].x-a[j].y;
a[j].x=a[j].x-a[j].y;
} //如果那个要剪的长方形横左边的差小于纵坐标，就交换那个给定的长方形的长跟宽
if(head->x[1]-head->x[0]>a[j].x && head->y[1]-head->y[0]>a[j].y)
{
printf("%d %I64d %I64d %I64d %I64d\n",d[j],head->x[0],head->y[0],head->x[0]+a[j].x,head->y[0]+a[j].y);
if(((head->x[1]-head->x[0]-a[j].x)*a[j].y)>(head->x[1]-head->x[0])*(head->y[1]-head->y[0]-a[j].y))
{
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0]+a[j].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[0]+a[j].y;
e1=(struct DE*)malloc(LEN);
e1->next=head;
head=e1;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+a[j].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
free(e2);
}
else
{
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+a[j].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
e1=(struct DE*)malloc(LEN);
e1->next=head;
head=e1;
head->x[0]=e2->x[0]+a[j].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[0]+a[j].y;
free(e2);
}//把纸面积最小的放在最前
a[j].x=0;a[j].y=0;
p=1;
k=k+2;
break;
}//如果被剪的矩形的长宽都小于那张纸的
else
if(head->x[1]-head->x[0]==a[j].x && head->y[1]-head->y[0]>a[j].y)
{
printf("%d %I64d %I64d %I64d %I64d\n",d[j],head->x[0],head->y[0],head->x[0]+a[j].x,head->y[0]+a[j].y);
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0];
head->y[0]=e2->y[0]+a[j].y;
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
free(e2);
a[j].x=0;a[j].y=0;//把纸面积最小的放在最前
k=k+1;
p=1;
break;
}//如果被剪的矩形的宽小于那张纸的，长等于那张纸
else
if(head->x[1]-head->x[0]>a[j].x && head->y[1]-head->y[0]==a[j].y)
{
printf("%d %I64d %I64d %I64d %I64d\n",d[j],head->x[0],head->y[0],head->x[0]+a[j].x,head->y[0]+a[j].y);
e1=(struct DE*)malloc(LEN);
e2=head;
head=e1;
head->next=e2->next;
head->x[0]=e2->x[0]+a[j].x;
head->y[0]=e2->y[0];
head->x[1]=e2->x[1];
head->y[1]=e2->y[1];
a[j].x=0;a[j].y=0;
free(e2);
k=k+1;
p=1;
break;
}//如果被剪的矩形的长小于那张纸的，宽等于那张纸
else
if(head->x[1]-head->x[0]==a[j].x && head->y[1]-head->y[0]==a[j].y)
{
printf("%d %I64d %I64d %I64d %I64d\n",d[j],head->x[0],head->y[0],head->x[0]+a[j].x,head->y[0]+a[j].y);
e2=head;
head=head->next;
free(e2);
a[j].x=0;a[j].y=0;
k=k;
p=1;
break;
}//如果被剪的矩形的长宽都等于那张纸的
if(a[j].x<a[j].y)
{
a[j].x=a[j].y+a[j].x;
a[j].y=a[j].x-a[j].y;
a[j].x=a[j].x-a[j].y;
}//恢复为原来长在前面，宽在后面
}
}
if(p==0 && i<k)
{
e2=head;
head=e2->next;
free(e2);
}
}
}
int main()//主函数
{
int i,j,n,d[2000];
long long b,c;
struct BC a[2000];
scanf("%I64d%I64d",&b,&c);
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%ld%ld",&a[i].x,&a[i].y);
if(c>b)
{
b=b+c;
c=b-c;
b=b-c;
} //使大的矩形的长在前面，宽在后面
for(i=0;i<n;i++)
if(a[i].x<a[i].y)
{
a[i].x=a[i].x+a[i].y;
a[i].y=a[i].x-a[i].y;
a[i].x=a[i].x-a[i].y;
} //使所有矩形长再前面，宽在后面
for(i=0;i<n;i++)
d[i]=i+1;
paixu(a,n,d);//对矩形面积进行排序
if(n<10)
meiju(a,n,d,b,c);
else
tanxin(a,n,d,b,c);
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -