[2019.3.12]BZOJ1033 [ZJOI2008]杀蚂蚁antbuster

蚂蚁antbuster"/>

[2019.3.12]BZOJ1033 [ZJOI2008]杀蚂蚁antbuster

两个**错误调了一整天...

1.pubp函数括号匹配错了

2.精度常数类型开成了int

就是一个大模拟,别的没什么好讲的,讲一讲我判断圆和线是否有交点的pubp函数,个人认为很容易理解。

其实就是不想动脑子才用了简单粗暴的办法

我们这样记录一条线段:

当该线段不与\(x\)轴垂直,我们记录\({k,b,l,r}\),表示这条线段所在的直线解析式为\(y=kx+b\),\(x\)坐标的范围为\([l,r]\)。

当该线段与\(x\)轴垂直,我们记录\(k,l,r\),表示这条线段所在的直线为\(x=k\),\(y\)坐标的范围为\([l,r]\)。

然后我们设点\(p(u,v)\),则以\(p\)为圆心,1为直径(\(\frac{1}{2}\)为半径)的圆的方程为\((x-u)^2+(y-v)^2=\frac{1}{4}\)。

我们要求线段和点\(p\)是否有交点,考虑求线段所在直线和\(p\)是否有交点,以及是否有交点的坐标在线段的坐标范围内。

当线段不与\(x\)轴垂直,我们设线段为\(k,b,l,r\)。

设交点坐标\((x,y)\)则有

\(kx+b=y\)(①)

\((x-u)^2+(y-v)^2=\frac{1}{4}\)(②)

展开②式

\(x^2-2ux+u^2+y^2-2vy+v^2-\frac{1}{4}=0\)

代入\(y=kx+b\)

\(x^2-2ux+u^2+(kx+b)^2-2v(kx+b)+v^2-\frac{1}{4}=0\)

\(x^2-2ux+u^2+k^2x^2+2bkx+b^2-2vkx-2vb+v^2-\frac{1}{4}=0\)

即

\((k^2+1)x^2+(2bk-2vk-2u)x+u^2+b^2-2vb+v^2-\frac{1}{4}\)

那么有\(x=\frac{-(2bk-2vk-2u)\pm\sqrt{(2bk-2vk-2u)^2-4(k^2+1)(u^2+b^2-2vb+v^2-\frac{1}{4})}}{2(k^2+1)}\)

设\(pt_1=-(2bk-2vk-2u),pt_2=\sqrt{(2bk-2vk-2u)^2-4(k^2+1)(u^2+b^2-2vb+v^2-\frac{1}{4})},pt_3=2(k^2+1)\)

则当\(l\le\frac{pt_1+pt_2}{pt_3}\le r\)或\(l\le\frac{pt_1-pt_2}{pt_3}\le r\)时

线段与圆有交点。

当线段与\(x\)轴垂直,我们设线段为\(k,l,r\)。

设交点坐标\((k,y)\)则有

\((k-u)^2+(y-v)^2=\frac{1}{4}\)

\((y-v)^2=\frac{1}{4}-(k-u)^2\)

\(y=v\pm\sqrt{\frac{1}{4}-(k-u)^2}\)

设\(pt_1=\sqrt{\frac{1}{4}-(k-u)^2}\)

则当\(l\le v+pt_1\le r\)或\(l\le v-pt_1\le r\)时

线段与圆有交点。

当然这种做法也有一定的缺点,比如式子比较复杂,容易写错或者出现精度问题。

其余部分直接模拟就好了。

code:

代码不长,刚好130行

使用vector来储存蚂蚁

#include<bits/stdc++.h>
#define sqr(x) (x)*(x)
using namespace std;
const double _=1e-7;
const int W[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct line{//y=kx+b(l<=x<=r)(tag=0);x=k(l<=y<=r)(tag=1)double k,b,l,r;int tag;
};
struct point{int x,y;
}turret[25];
struct ant{point p,lst;int hp,mxhp,age,level;
};
bool equ(const double&x,const double&y){return abs(x-y)<=_;
}
bool les(const double&x,const double&y){return y-x>_;
}
bool eol(const double&x,const double&y){return equ(x,y)||les(x,y);
}
double dis(point a,point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
line solve(point a,point b){//求出线段ab的表示if(a.x==b.x)return(line){a.x,0,min(a.y,b.y),max(a.y,b.y),1};else{double k=1.0*(a.y-b.y)/(a.x-b.x);return(line){k,a.y-k*a.x,min(a.x,b.x),max(a.x,b.x),0};}
}
bool pubp(line l,point p){//判断线段l与以点p为圆心,1为直径的圆是否有交点if(!l.tag){if(sqr(2*l.k*l.b-2*p.y*l.k-2*p.x)-4*(sqr(l.k)+1)*(sqr(p.x)+sqr(l.b)-2*p.y*l.b+sqr(p.y)-1.0/4.0)<0)return false;double pt1=-(2*l.k*l.b-2*p.y*l.k-2*p.x),pt2=sqrt(sqr(2*l.k*l.b-2*p.y*l.k-2*p.x)-4*(sqr(l.k)+1)*(sqr(p.x)+sqr(l.b)-2*p.y*l.b+sqr(p.y)-1.0/4.0)),pt3=2*(sqr(l.k)+1);return(eol(l.l,(pt1+pt2)/pt3)&&eol((pt1+pt2)/pt3,l.r)||eol(l.l,(pt1-pt2)/pt3)&&eol((pt1-pt2)/pt3,l.r));}else{if(sqr(l.k-p.x)>1.0/4.0)return false;int pt1=sqrt(1.0/4.0-sqr(l.k-p.x));return(eol(l.l,p.y+pt1)&&eol(p.y+pt1,l.r))||(eol(l.l,p.y-pt1)&&eol(p.y-pt1,l.r));}
}
int n,m,s,d,r,t,ph[10][10],mp[10][10];
int stot,tca=-1;
vector<ant>a;
void getp(point&x){//读入点 int t1,t2;scanf("%d%d",&t1,&t2),x.x=t1,x.y=t2;mp[t1][t2]=1;
}
double POW(double x,int y){//快速幂 double tot=1;while(y)y&1?tot*=x:0,x*=x,y>>=1;return tot;
}
void Spawn(){//生成蚂蚁 if(mp[0][0])return;for(int i=0;i<a.size();++i)if(a[i].p.x==0&&a[i].p.y==0)return;++stot;int tmp=(int)(4.0*POW(1.1,(stot+5)/6));a.push_back((ant){(point){0,0},(point){0,0},tmp,tmp,0,(stot+5)/6});
}
void Put_pheromone(){//留下信息素 for(int i=0;i<a.size();++i)ph[a[i].p.x][a[i].p.y]+=(tca==i?5:2);
}
bool Blank(int x,int y){//判断一个点是否为空(即没有炮塔或者蚂蚁) if(mp[x][y])return false;for(int i=0;i<a.size();++i)if(a[i].p.x==x&&a[i].p.y==y)return false;return true;
}
bool Check(int id,int x,int y){//判断一个点是否可行 return (x!=a[id].lst.x||y!=a[id].lst.y)&&0<=x&&x<=n&&0<=y&&y<=m&&Blank(x,y);
}
void Move_to(int id,int x,int y){//将蚂蚁移动到点(x,y) a[id].lst=a[id].p,a[id].p=(point){x,y};
}
void Move(){//移动蚂蚁 for(int i=0;i<a.size();++i){int mxp=-1,tw,tx,ty;for(int w=0;w<4;++w)tx=a[i].p.x+W[w][0],ty=a[i].p.y+W[w][1],Check(i,tx,ty)&&ph[tx][ty]>mxp?mxp=ph[tx][ty],tw=w:0;if(mxp<0){a[i].lst=a[i].p;continue;}else{if((a[i].age+1)%5==0)while(tw=(tw+3)%4,!Check(i,a[i].p.x+W[tw][0],a[i].p.y+W[tw][1]));Move_to(i,a[i].p.x+W[tw][0],a[i].p.y+W[tw][1]);}}
}
void Shoot(point u,point v){//从点u发射激光到点v line ray=solve(u,v);for(int i=0;i<a.size();++i)if(pubp(ray,a[i].p))a[i].hp-=d;
}
void Attack(){//炮塔攻击 for(int i=1;i<=s;++i){if(tca!=-1&&eol(dis(turret[i],a[tca].p),(double)r))Shoot(turret[i],a[tca].p);else{double mnd=r+1,td;int sa;for(int j=0;j<a.size();++j)td=dis(turret[i],a[j].p),les(td,mnd)?mnd=td,sa=j:0;if(eol(mnd,r))Shoot(turret[i],a[sa].p);}}
}
void End(int T){//游戏结束 printf("Game over after %d seconds\n%d\n",T,a.size());for(int i=0;i<a.size();++i)printf("%d %d %d %d %d\n",a[i].age,a[i].level,a[i].hp,a[i].p.x,a[i].p.y);exit(0);
}
int main(){scanf("%d%d%d%d%d",&n,&m,&s,&d,&r);for(int i=1;i<=s;++i)getp(turret[i]);scanf("%d",&t);for(int Time=1;Time<=t;++Time){if(a.size()<6)Spawn();Put_pheromone(),Move();for(int i=0;i<a.size();++i)if(a[i].p.x==n&&a[i].p.y==m&&tca==-1)tca=i,a[i].hp=min(a[i].mxhp,a[i].hp+a[i].mxhp/2);Attack();for(int i=0;i<a.size();++i)if(a[i].hp<0)a.erase(a.begin()+i),tca==i?tca=-1:0,tca>i?--tca:0,--i;for(int i=0;i<a.size();++i)if(tca==i&&a[i].p.x==0&&a[i].p.y==0)End(Time);for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)ph[i][j]?--ph[i][j]:0;for(int i=0;i<a.size();++i)++a[i].age;}printf("The game is going on\n%d\n",a.size());for(int i=0;i<a.size();++i)printf("%d %d %d %d %d\n",a[i].age,a[i].level,a[i].hp,a[i].p.x,a[i].p.y);return 0;
}

转载于:.html