http://acm.pku.edu.cn/JudgeOnline/problem?id=1116
Код:
#include "stdio.h" int xn,yn1,xt,yt,n,ne[100][5]; int getres(int res[2],int i,int j){ int l1,l2; l1=ne[i][3]+ne[i][1]; l2=ne[i][4]+ne[i][1]; if(l2<=j){ if(j>=ne[i][2]&&2*j-ne[i][2]>=2*l1) return 0; if(ne[i][2]-j>=0&&2*(l1)<=j)res[1]+=ne[i][2]-j; else res[1]+=ne[i][2]-2*(j-l1); return 0; } if(l1>=j+xt){ if(ne[i][2]+j+xt<=xn&&2*(j+xt)+ne[i][2]<=2*l2)return 0; if(ne[i][2]+j+xt>=xn&&xn+j+xt<=2*l2)res[1]+=ne[i][2]-xn+j+xt; else res[1]+=ne[i][2]-2*(l2-j-xt); return 0; } res[0]+=1; if(l1<=j&&l2>=j+xt){ if(j+xt==xn&&j==0){res[0]+=1; res[1]+=ne[i][2]; return 0;} if(j>=xn-j-xt){ if(j<ne[i][2])res[1]+=ne[i][2]-j; } else{ if(j+xt+ne[i][2]>xn) res[1]+=j+xt+ne[i][2]-xn; } return 0; } if(l1>j&&l2<j+xt){ res[0]+=1; res[1]+=ne[i][2]; return 0; } if(l1>j&&j+xt!=xn){ if(j+xt+ne[i][2]>xn) res[1]+=j+xt+ne[i][2]-xn; return 0; } if(l2<j+xt&&j!=0){ if(j<ne[i][2])res[1]+=ne[i][2]-j; return 0; } res[0]+=1;res[1]+=ne[i][2]; return 0; } void done(int ni,int res[2],int j){ int i,flag; for(i=0;i<n;i++){ flag=0; if(i==ni) continue; if(ne[i][0]>ne[ni][0]&&ne[ni][0]+yt>ne[i][0]){ if(ne[i][1]+ne[i][2]>j&&ne[i][1]+ne[i][2]<=j+xt) flag=1; else if(ne[i][1]<j+xt&&j<=ne[i][1])flag=1; else if(ne[i][1]<=j&&ne[i][1]+ne[i][2]>=j+xt)flag=1; } if(flag)getres(res,i,j); } return ; } void place(){ int l1,l2; int i,j,k,l,m,res[2]; int ros,inch; ros=1000,inch=10000; for(i=0;i<n;i++) if(yn1-ne[i][0]>=yt&&ne[i][2]>=xt){ l1=ne[i][3]+ne[i][1]; l2=ne[i][4]+ne[i][1]; if(l1+ne[i][2]/2<l2){j=l2-ne[i][2]; k=l1+ne[i][2];} else {j=l1-ne[i][2]/2; k=l2+ne[i][2]/2;} if(j<0) j=0; if(k>xn) k=xn; l=j;m=k-xt; for(;j+xt<=k;j++){ res[0]=0;res[1]=0; done(i,res,j); if(res[0]==0&&res[1]==0) {printf("0 0\n"); return ;} if(ros>res[0]){ros=res[0];inch=res[1];} else if(res[0]==ros&&res[1]<inch)inch=res[1]; } j=l1-ne[i][2]; if(j<0)j=0; k=l2+ne[i][2]; if(k>xn)k=xn; for(;j+xt<=k;j++){ if(j==l) {j=m; continue ;} res[0]=1;res[1]=0; done(i,res,j); if(res[0]==1&&res[1]==0) {printf("1 0\n"); return ;} if(ros>res[0]){ros=res[0];inch=res[1];} else if(res[0]==ros&&res[1]<inch)inch=res[1]; } } printf("%d %d\n",ros,inch); return ; } int main(){ int i; scanf("%d%d%d%d",&xn,&yn1,&xt,&yt); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d%d%d%d",&ne[i][0],&ne[i][1],&ne[i][2],&ne[i][3],&ne[i][4]); place(); return 0; }