社区讨论

萌新刚学OI,不是妹子,求助

P2586[ZJOI2008] 杀蚂蚁参与者 11已保存回复 15

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
15 条
当前快照
1 份
快照标识符
@mi7wlcu3
此快照首次捕获于
2025/11/21 04:48
4 个月前
此快照最后确认于
2025/11/21 06:34
4 个月前
查看原帖
RT
CPP
#include<bits/stdc++.h>
#define sqr(x) (x)*(x)
using namespace std;
const int _=1e-9;
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){//求线段方程 
	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){//判断直径为1,圆心为p的圆与线段l是否有交 
	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&&(pt1+pt2)/pt3<=l.r)||eol(l.l,(pt1-pt2)/pt3&&(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(){//生成蚂蚁 
	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){//蚂蚁i移动到(x,y) 
	a[id].lst=a[id].p,a[id].p=(point){x,y};
}
void Move(){//蚂蚁移动 
	for(int i=0,w;i<a.size();++i){
		int mxp=-1,tw,tx,ty;
		for(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{
			w=tw;
			if((a[i].age+1)%5==0)while(w=(w+3)%4,!Check(i,a[i].p.x+W[w][0],a[i].p.y+W[w][1]));
			Move_to(i,a[i].p.x+W[w][0],a[i].p.y+W[w][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&&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),td<mnd?mnd=td,sa=j:0;
			if(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;
}

回复

15 条回复,欢迎继续交流。

正在加载回复...