mdzzhhhhhhh…..
这题真恶心，猪国杀一轮只有一只猪在动，而这个一轮6只蚂蚁，最多20台炮。。。其实题目应该叫 “（被）蚂蚁杀”。
不得不提几个坑：
1.通过样例注意一下蚂蚁的年龄。
2.蚂蚁搬着蛋糕走到了洞口时，这一秒还没有结束，如果这一秒结束时炮把他打死了，那蛋糕也要归为。
3.计算斜率时斜率不存在。。。我貌似没学过几何QAQ
4.如何计算圆到线段距离：因为不能把蚂蚁射穿。但都是整点，所以用炮和目标蚂蚁的横纵坐标构造一个矩形，圆心在这个矩形内部的才可能被打到。
5.我开double过不去，得开float。。。
6.如果一个蚂蚁卡住不动一秒，那他下一秒可以往回走。
7.蛋糕传回去后，如果(n,m)上有一只蚂蚁，那他不会把蛋糕搬起来，只有在下一秒移动后有蚂蚁在那里才会搬起来。记得考虑有一个蚂蚁困在（n，m）了一秒，之后他把蛋糕搬起来了。。。。
8.蚂蚁洞上有蚂蚁时不会生蚂蚁。
也就这几个坑吧，，，也许是我脑洞太大，错了太多。
无注释的（下面有一个有注释的）
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200005
#define fl float
using namespace std;
struct zb
{
int x,y;
friend bool operator ==(zb a,zb b){
if(a.x==b.x&&a.y==b.y)return 1;
return 0;
}
zb(){}
zb(int x_,int y_){x=x_;y=y_;}
}bomb[25],Cake,Cave;
struct Ant{int t,old,blood,lv;zb last,now;}ant[N];
int n,m,t,hurt,r,sum_b,nex[N],fro[N];//s->炮塔数量，d->伤害，r->攻击半径
int ant_sum,ant_now,boss;
int smell[10][10],map[10][10];//1->ant,2->bomb,3->cake
int turn[4][2]={0,1,1,0,0,-1,-1,0};
fl level[100000];
int hahaha(int x)
{
int l=level[ant[x].lv];
ant[x].blood+=l/2;
if(ant[x].blood>l)ant[x].blood=l;
}
void delieve(int T)
{
if(map[0][0])return;
int l=++ant_now,v=(l-1)/6+1;
ant_sum++;map[0][0]=1;
ant[l].now=zb(0,0); ant[l].last=zb(-1,-1);
ant[l].t=T; ant[l].old=1;
ant[l].blood=level[v]; ant[l].lv=v;
}
bool check(zb x,zb last)
{
if(x.x<0||x.x>n||x.y<0||x.y>m)return 0;
if(map[x.x][x.y]!=0)return 0;
if(x==last)return 0;
return 1;
}
void mad_turn(int x,int To,zb zz)
{
for(int i=To-1;;i--)
{
if(i<0)i=3;
zb to=zb(ant[x].now.x+turn[i][0],ant[x].now.y+turn[i][1]);
if(check(to,zz)==1){ant[x].now=to;return;}
}
}
void move(int x)
{
int To=4,infor=-1;zb zz=ant[x].last;ant[x].last=ant[x].now;
for(int i=0;i<4;i++)
{
zb to=zb(ant[x].now.x+turn[i][0],ant[x].now.y+turn[i][1]);
if(!check(to,zz))continue;
if(smell[to.x][to.y]>infor)To=i,infor=smell[to.x][to.y];
}
if(To==4)
{
if(!boss&&Cake==ant[x].now){boss=x;hahaha(x);}
if(boss==x)Cake=ant[x].now;
map[ant[x].last.x][ant[x].last.y]=0;
map[ant[x].now.x][ant[x].now.y]=1;
return;
}
if(ant[x].old%5==0)mad_turn(x,To,zz);
else ant[x].now=zb(ant[x].now.x+turn[To][0],ant[x].now.y+turn[To][1]);
if(!boss&&Cake==ant[x].now){boss=x;hahaha(x);}
if(boss==x)Cake=ant[x].now;
map[ant[x].last.x][ant[x].last.y]=0;
map[ant[x].now.x][ant[x].now.y]=1;
}
void smellchange()
{
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(smell[i][j]!=0)smell[i][j]--;
}
void dead(int x)
{
nex[fro[x]]=nex[x];fro[nex[x]]=fro[x];
ant_sum--;map[ant[x].now.x][ant[x].now.y]=0;
if(boss==x){boss=0;Cake=zb(n,m);}
}
fl get_l(zb x,zb y){return (fl)sqrt(pow(x.x-y.x,2)+pow(x.y-y.y,2));}
fl MDZZ(fl a,fl b,fl c,zb x){return abs((fl)a*x.x+b*x.y+c)/sqrt(a*a+b*b);}
void get_hurt(zb x,zb y)
{
int x1=max(x.x,y.x),x2=min(x.x,y.x),y1=max(x.y,y.y),y2=min(x.y,y.y);
fl a,b,c;
a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y;
for(int i=nex[0];i<=ant_now;i=nex[i])
{
zb now=ant[i].now;
if(now.x<x2||now.x>x1||now.y>y1||now.y<y2)continue;
fl len=MDZZ(a,b,c,now);
if(len>0.5)continue;
ant[i].blood-=hurt;
}
}
int which(int x)
{
fl L=1000;int to=0;
for(int i=nex[0];i<=ant_now;i=nex[i])
{
fl l=get_l(bomb[x],ant[i].now);
if(l>(fl)r)continue;
if(i==boss)return i;
if(l<L)L=l,to=i;
}
return to;
}
void attack(int x)
{
int to=which(x);
if(to!=0)get_hurt(bomb[x],ant[to].now);
}
int play()
{
for(int u=1;u<=t;u++)
{
if(ant_sum!=6)delieve(u);
for(int i=nex[0];i<=ant_now;i=nex[i])
{
if(boss!=i)smell[ant[i].now.x][ant[i].now.y]+=2;
else smell[ant[i].now.x][ant[i].now.y]+=5;
}
for(int i=nex[0];i<=ant_now;i=nex[i])move(i);
for(int i=1;i<=sum_b;i++)attack(i);
for(int i=nex[0];i<=ant_now;i=nex[i])
if(ant[i].blood<0)dead(i);
smellchange();
if(Cake==Cave)return u;
for(int i=nex[0];i<=ant_now;i=nex[i])ant[i].old++;
}
return 0;
}
void init()
{
scanf("%d%d%d%d%d",&n,&m,&sum_b,&hurt,&r);
for(int i=1;i<=sum_b;i++)
scanf("%d%d",&bomb[i].x,&bomb[i].y),map[bomb[i].x][bomb[i].y]=2;
scanf("%d",&t);
ant_now=ant_sum=boss=0;
Cake=zb(n,m);Cave=zb(0,0);
for(int i=1;i<=t;i++)nex[i]=i+1,fro[i]=i-1;nex[0]=1;
int l=(t-1)/6+1;level[0]=4;
for(int i=1;i<=l;i++)level[i]=level[i-1]*1.1;
}
void jieshu()
{
int hh=play();
if(!hh)printf("The game is going on
");
else printf("Game over after %d seconds
",hh);
printf("%d
",ant_sum);int s=0;
for(int i=nex[0];i<=ant_now;i=nex[i])
printf("%d %d %d %d %d
",ant[i].old-1,ant[i].lv,ant[i].blood,ant[i].now.x,ant[i].now.y);
}
int yjn()
{
freopen("antbuster_ex.in","r",stdin);
freopen("antbuster_ex.out","w",stdout);
init();jieshu();
}
int qty=yjn();
int main(){;}有注释的
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 200005
#define fl float
using namespace std;
struct zb
{
int x,y;
friend bool operator ==(zb a,zb b)
{
if(a.x==b.x&&a.y==b.y)return 1;
return 0;
}
zb(){}
zb(int x_,int y_){x=x_;y=y_;}
}bomb[25],Cake,Cave;
struct Ant{int t,old,blood,lv;zb last,now;}ant[N];
int n,m,t,hurt,r,sum_b,nex[N],fro[N];//s->炮塔数量，d->伤害，r->攻击半径
int ant_sum,ant_now,boss;
int smell[10][10],map[10][10];//1->ant,2->bomb,3->cake
int turn[4][2]={0,1,1,0,0,-1,-1,0};
fl level[100000];
int hahaha(int x)
{
int l=level[ant[x].lv];
ant[x].blood+=l/2;
if(ant[x].blood>l)ant[x].blood=l;
//printf("boss %d's blood becomes %d!
",x,ant[x].blood);
}
void delieve(int T)
{
if(map[0][0])return;
int l=++ant_now,v=(l-1)/6+1;
ant_sum++;map[0][0]=1;
ant[l].now=zb(0,0); ant[l].last=zb(-1,-1);
ant[l].t=T; ant[l].old=1;
ant[l].blood=level[v]; ant[l].lv=v;
//printf("There is a new ant! he is %d
",l);
}
bool check(zb x,zb last)
{
if(x.x<0||x.x>n||x.y<0||x.y>m)return 0;
if(map[x.x][x.y]!=0)return 0;
if(x==last)return 0;
return 1;
}
void mad_turn(int x,int To,zb zz)
{
//printf("ant%d is going on a mad turn!
",x);
for(int i=To-1;;i--)
{
if(i<0)i=3;
zb to=zb(ant[x].now.x+turn[i][0],ant[x].now.y+turn[i][1]);
if(check(to,zz)==1){ant[x].now=to;return;}
}
}
void move(int x)
{
int To=4,infor=-1;zb zz=ant[x].last;ant[x].last=ant[x].now;
for(int i=0;i<4;i++)
{
zb to=zb(ant[x].now.x+turn[i][0],ant[x].now.y+turn[i][1]);
//printf("Where does ant%d want to go (%d,%d)
",x,to.x,to.y);
if(!check(to,zz))continue;
if(smell[to.x][to.y]>infor)To=i,infor=smell[to.x][to.y];
}
if(To==4)
{
//printf("This ant couldn't move
");
if(!boss&&Cake==ant[x].now)
{
//printf("now ant%d takes the cake with him!
",x);
boss=x;hahaha(x);
}
if(boss==x)Cake=ant[x].now;
map[ant[x].last.x][ant[x].last.y]=0;
map[ant[x].now.x][ant[x].now.y]=1;
return;
} //
if(ant[x].old%5==0)mad_turn(x,To,zz);
else ant[x].now=zb(ant[x].now.x+turn[To][0],ant[x].now.y+turn[To][1]);
//printf("ant%d (%d,%d)--->(%d,%d)
",x,ant[x].last.x,ant[x].last.y,ant[x].now.x,ant[x].now.y);
if(!boss&&Cake==ant[x].now)
{
//printf("now ant%d takes the cake with him!
",x);
boss=x;hahaha(x);
}
if(boss==x)Cake=ant[x].now;
map[ant[x].last.x][ant[x].last.y]=0;
map[ant[x].now.x][ant[x].now.y]=1;
}
void smellchange()
{
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
if(smell[i][j]!=0)smell[i][j]--;
}
void dead(int x)
{
// printf("ant%d dead!
",x);
nex[fro[x]]=nex[x];fro[nex[x]]=fro[x];
ant_sum--;map[ant[x].now.x][ant[x].now.y]=0;
if(boss==x)
{
//printf("now cake is back
");
boss=0;Cake=zb(n,m);
}
}
fl get_l(zb x,zb y){return (fl)sqrt(pow(x.x-y.x,2)+pow(x.y-y.y,2));}
fl MDZZ(fl a,fl b,fl c,zb x){return abs((fl)a*x.x+b*x.y+c)/sqrt(a*a+b*b);}
void get_hurt(zb x,zb y)
{
int x1=max(x.x,y.x),x2=min(x.x,y.x),y1=max(x.y,y.y),y2=min(x.y,y.y);
fl a,b,c;
a=y.y-x.y; b=x.x-y.x; c=y.x*x.y-x.x*y.y;
for(int i=nex[0];i<=ant_now;i=nex[i])
{
zb now=ant[i].now;
if(now.x<x2||now.x>x1||now.y>y1||now.y<y2){continue;}//printf("ant%d is far from the line
",i);
fl len=MDZZ(a,b,c,now);
//printf("the len ant%d is %f
",i,len);
if(len>0.5)continue;
//printf("ant%d is hurt
",i);
ant[i].blood-=hurt;
}
}
int which(int x)
{
fl L=1000;int to=0;
for(int i=nex[0];i<=ant_now;i=nex[i])
{
fl l=get_l(bomb[x],ant[i].now);
// printf("len between bomb%d and ant%d is %f
",x,i,l);
if(l>(fl)r)continue;
if(i==boss)return i;
if(l<L)L=l,to=i;
}
return to;
}
void attack(int x)
{
int to=which(x);
//printf("bomb%d---->ant%d!
",x,to);
if(to!=0)get_hurt(bomb[x],ant[to].now);
}
int play()
{
for(int u=1;u<=t;u++)
{
//printf("
What's the time now %d
",u);
if(ant_sum!=6)delieve(u);
for(int i=nex[0];i<=ant_now;i=nex[i])
{
if(boss!=i)smell[ant[i].now.x][ant[i].now.y]+=2;
else smell[ant[i].now.x][ant[i].now.y]+=5;
}
// printf("So now,Cake is at (%d,%d)
boss is %d
",Cake.x,Cake.y,boss); //
/* printf("there are %d ants on the ground
",ant_sum); //
for(int i=nex[0];i<=ant_now;i=nex[i])
{
printf("ant %d: ",i);
printf("Old %d Lv%d Blood %d Where(%d,%d)
",ant[i].old,ant[i].lv,ant[i].blood,ant[i].now.x,ant[i].now.y);
}*/
for(int i=nex[0];i<=ant_now;i=nex[i])
{
//printf("ant%d move
",i); //
move(i);
}
/* printf("information
");
for(int i=0;i<=n;i++,printf("
"))
for(int j=0;j<=m;j++)
printf("%d ",smell[i][j]);
printf("map
");
for(int i=0;i<=n;i++,printf("
"))
for(int j=0;j<=m;j++)
if(map[i][j]==1)printf("A ");
else if(map[i][j]==2)printf("B ");
else printf("0 ");*/
for(int i=1;i<=sum_b;i++)
{
// printf("bomb%d attack
",i);
attack(i);
}
for(int i=nex[0];i<=ant_now;i=nex[i])
if(ant[i].blood<0)dead(i);
smellchange();
if(Cake==Cave)return u;
for(int i=nex[0];i<=ant_now;i=nex[i])ant[i].old++;
/* for(int i=nex[0];i<=ant_now;i=nex[i])
{
printf("ant %d: ",i);
printf("Old %d Lv%d Blood %d Where(%d,%d)
",ant[i].old,ant[i].lv,ant[i].blood,ant[i].now.x,ant[i].now.y);
}*/
//if(u==82)system("pause");
}
return 0;
}
void init()
{
scanf("%d%d%d%d%d",&n,&m,&sum_b,&hurt,&r);
for(int i=1;i<=sum_b;i++)scanf("%d%d",&bomb[i].x,&bomb[i].y),map[bomb[i].x][bomb[i].y]=2;
scanf("%d",&t);ant_now=ant_sum=boss=0;Cake=zb(n,m);Cave=zb(0,0);
for(int i=1;i<=t;i++)nex[i]=i+1,fro[i]=i-1;nex[0]=1;
int l=(t-1)/6+1;level[0]=4;for(int i=1;i<=l;i++)level[i]=level[i-1]*1.1;
}
void jieshu()
{
int hh=play();
if(!hh)printf("The game is going on
");
else printf("Game over after %d seconds
",hh);
printf("%d
",ant_sum);int s=0;
for(int i=nex[0];i<=ant_now;i=nex[i])
printf("%d %d %d %d %d
",ant[i].old-1,ant[i].lv,ant[i].blood,ant[i].now.x,ant[i].now.y);
}
int main()
{
init();
jieshu();
}