 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
学习中.......,看了别人简洁的代码，才发现自己的代码（下面）是如此差劲 （WA看似必然)。。。。。#include<iostream>
using namespace std;
float xn,yn,xt,yt;
float y[101];
float x[101];
float l[101];
float x1[101];
float x2[101];
int nl;
int bestl;
int bestp;
bool tag[10001];
void input()
{
cin>>xn>>yn>>xt>>yt;
cin>>nl;
int i;
for(i=0;i<nl;i++)
{
cin>>y[i]>>x[i]>>l[i]>>x1[i]>>x2[i];
x1[i]+=x[i];
x2[i]+=x[i];
}
}
void cut(float L,float R,int i,int &curl,int &curp)
{
float d,dl,dr,dm,dmin,lm,ll,rr;
ll=x[i];
rr=x[i]+l[i];
if(rr<=L||ll>=R)return;//当大书和架子没有冲突
if((x1[i]>L&&x2[i]<R)||(xt==xn))//当两颗钉子和大书有冲突，撤销钉子和架子
{
curl+=(int)(l[i]);
curp+=2;
return;
}
if(x1[i]>=R)//当左边的钉子坐标大于大书的右边，不用移动钉子
{
d=x2[i]-x1[i];;
dr=xn-x2[i];
dl=x1[i]-R;
if(dr>dl)
{
dm=dr;
dmin=dl;
}
else
{
dm=dl;
dmin=dr;
}
lm=d+2*dmin;
dm=dm-dmin;
if(dm>d)dm=d;
lm+=dm;
if(l[i]<=lm)return;
else
{
curl+=(int)(l[i]-lm+0.5);
return;
}
}
if(x2[i]<=L)//当右边的钉子小于大书的左边
{
d=x2[i]-x1[i];
dr=L-x2[i];
dl=x1[i];
if(dr>dl)
{
dm=dr;
dmin=dl;
}
else
{
dm=dl;
dmin=dr;
}
lm=d+2*dmin;
dm=dm-dmin;
if(dm>d)dm=d;
lm+=dm;
if(l[i]<=lm)return;
else
{
curl+=(int)(l[i]-lm+0.5);
return;
}
}
if(x2[i]<R)//x[i]<=L当右边的钉子小于大书的右边，但左边的钉子小于等于大书的左边
{
lm=L;
curp++;
if(lm==0)curp++;
if(l[i]<=lm)return;
else
{
curl+=(int)(l[i]-lm+0.5);
return;
}
}
if(x1[i]>L)//x2[i]>=R左边的钉子大于大书的左边，但右边的钉子大于大书的右边
{
lm=xn-R;
curp++;
if(lm==0)curp++;
if(l[i]<=lm)return;
else
{
curl+=(int)(l[i]-lm+0.5);
return;
}
}
if(x1[i]<=L&&x2[i]>=R)//分布在两侧的钉子
{
curp++;
lm=L;
dr=xn-R;
if(L<dr)lm=dr;
if(lm==0)curp++;
if(l[i]<=lm)return;
else
{
curl+=(int)(l[i]-lm+0.5);
return;
}
}
}
void process()
{
float L,R,Lmin,Lmax,Rmin,Rmax,lrange;
int i,j,k,start,end,PLmin,PLmax,PRmin,PRmax,p;
int curl,curp;
bestp=10000;
bestl=0;
for(i=0;i<nl;i++)
{
if(y[i]+yt>yn)continue;
if(l[i]<xt)continue;
Lmin=x1[i]-xt/2;
Lmax=x2[i]-xt/2;
Rmin=x1[i]+xt/2;
Rmax=x2[i]+xt/2;
PLmin=(int)(x1[i]-l[i]);//position of peg;
PLmax=(int)(x1[i]+l[i]);
PRmin=(int)(x2[i]-l[i]);
PRmax=(int)(x2[i]+l[i]);
memset(tag,false,sizeof(tag));//每个位置只枚举一次
if(Lmax>=0&&Rmin<=xn)
{
start=(int)Lmin;
end=(int)Lmax;
if(start<0)start=0;
if(end>xn)end=(int)xn;
for(j=start;j<=end;j++)//枚举左端坐标
{
L=j;
R=L+xt;
if(R>xn)break;
if(R>x1[i]+l[i])break;
if(x1[i]-L>l[i])continue;
curl=0;
curp=0;
tag[j]=true;
for(k=0;k<nl;k++)//检查其它架子
{
if(k==i)continue;
if(y[k]<y[i]||(y[k]>=y[i]+yt))continue;
cut(L,R,k,curl,curp);
}
if(curp==bestp)
{
if(curl<bestl)bestl=curl;
}
else if(curp<=bestp)
{
bestp=curp;
bestl=curl;
}
}
start=(int)(PLmin-xt/2);
if(start<0)start=0;
end=(int)(PLmax-xt/2);
if(end>xn)end=(int)xn;
for(j=start;j<=end;j++)//枚举左端坐标
{
L=j;
if(tag[j])continue;
R=L+xt;
if(R>xn)break;
curl=0;
curp=1;
tag[j]=true;
for(k=0;k<nl;k++)//检查其它架子
{
if(k==i)continue;
if(y[k]<y[i]||(y[k]>=y[i]+yt))continue;
cut(L,R,k,curl,curp);
}
if(curp==bestp)
{
if(curl<bestl)bestl=curl;
}
else if(curp<=bestp)
{
bestp=curp;
bestl=curl;
}
}
start=(int)(PRmin-xt/2);
if(start<0)start=0;
end=(int)(PRmax-xt/2);
if(end>xn)end=(int)xn;
for(j=start;j<=end;j++)//枚举左端坐标
{
L=j;
if(tag[j])continue;
R=L+xt;
if(R>xn)break;
curl=0;
curp=1;
for(k=0;k<nl;k++)//检查其它架子
{
if(k==i)continue;
if(y[k]<y[i]||(y[k]>=y[i]+yt))continue;
cut(L,R,k,curl,curp);
}
if(curp==bestp)
{
if(curl<bestl)bestl=curl;
}
else if(curp<=bestp)
{
bestp=curp;
bestl=curl;
}
}
}
}
}
int main()
{
input();
process();
cout<<bestp<<" "<<bestl<<endl;
//system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
