| 记录编号 |
460262 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[ZJOI 2008] 杀蚂蚁 (完整版) |
最终得分 |
100 |
| 用户昵称 |
 BaDBoY |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.780 s |
| 提交时间 |
2017-10-16 19:29:33 |
内存使用 |
1.84 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define eps 1e-9
int Map[9][9],s,d,t,r,n,m,tot,antcnt,Infor[9][9],cake,T;
int dx[5]={-1,0,1,0},dy[5]={0,-1,0,1};
struct GUN{int x,y;} gun[25];
double qx[200005];
bool End;
int dcmp(double x) {
if (x<=eps&&x>=-eps) return 0;
return (x>0)?1:-1;
}
struct ANT {
int x,y,lastx,lasty,age,level,startblood,blood;
bool carry;
} ant[10];
struct Point {
double x,y;
Point(double X=0,double Y=0) {x=X,y=Y;}
};
Point operator + (Point a,Point b) {return Point(a.x+b.x,a.y+b.y);}
Point operator - (Point a,Point b) {return Point(a.x-b.x,a.y-b.y);}
bool operator == (Point a,Point b) {return a.x==b.x&&a.y==b.y;}
double Dot(Point a,Point b){return a.x*b.x+a.y*b.y;}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
double Len(Point a){return sqrt(a.x*a.x+a.y*a.y);}
double DisTS(Point P,Point A,Point B) {
if (A==B) return Len(P-A);
Point v=B-A,w=P-A,u=P-B;
if (dcmp(Dot(v,w))<0) return Len(w);
else if (dcmp(Dot(v,u))>0) return Len(u);
else return fabs(Cross(v,w)/Len(v));
}
void Birth() {
if(antcnt<6&&!Map[0][0]) {
++antcnt,++tot,++Map[0][0];
ant[antcnt].x=ant[antcnt].y=ant[antcnt].lastx=ant[antcnt].lasty=0;
ant[antcnt].age=1,ant[antcnt].level=(tot-1)/6+1;
ant[antcnt].startblood=ant[antcnt].blood=floor(4*qx[ant[antcnt].level]);
ant[antcnt].carry=false;
}
}
void Add_Information() {
for (int i=1; i<=antcnt; ++i) {
if (ant[i].carry) Infor[ant[i].x][ant[i].y]+=5;
else Infor[ant[i].x][ant[i].y]+=2;
}
}
void Carry() {
if(cake) return ;
for(int i=1; i<=antcnt; ++i) {
if(ant[i].x==n&&ant[i].y==m) {
ant[i].carry=true,cake=i;
ant[i].blood+=ant[i].startblood/2;
ant[i].blood=min(ant[i].blood,ant[i].startblood);
break;
}
}
}
void CheckDeath() {
int i=1;
while(i<=antcnt) {
if(ant[i].blood<0) {
--Map[ant[i].x][ant[i].y];
for(int j=i; j<antcnt; ++j) ant[j]=ant[j+1];
--antcnt;
} else ++i;
} cake=0;
for(i=1; i<=antcnt; ++i) {
if (ant[i].carry) {
cake=i;
break;
}
}
}
bool Check_end() {
if(!cake) return false;
for(int i=1; i<=antcnt; ++i) if(!ant[i].x&&!ant[i].y&&ant[i].carry) return true;
return false;
}
void Change() {
for(int i=0; i<=n; ++i) {
for(int j=0; j<=m; ++j) if(Infor[i][j]) --Infor[i][j];
}
for(int i=1; i<=antcnt; ++i) ++ant[i].age;
}
void Move() {
for(int dir=0,i=1,Max=0,canmove=0; i<=antcnt; ++i,Max=0,canmove=0,dir=0) {
int x=ant[i].x,y=ant[i].y;
int lastx=ant[i].lastx,lasty=ant[i].lasty;
bool move[4]={0};
memset(move,0,sizeof(move));
for(int j=0; j<4; ++j) {
int nxtx=x+dx[j],nxty=y+dy[j];
if(nxtx>=0&&nxtx<=n&&nxty>=0&&nxty<=m&&!Map[nxtx][nxty]&&(nxtx!=lastx||nxty!=lasty)) {
move[j]=1;
++canmove;
Max=max(Max,Infor[nxtx][nxty]);
}
}
if(!canmove) {ant[i].lastx=x;ant[i].lasty=y;continue;}
for(int j=3; j>=0; --j) {
int nxtx=x+dx[j],nxty=y+dy[j];
if(move[j]&&Infor[nxtx][nxty]==Max) {
dir=j;
if(ant[i].age%5==0) break;
--Map[x][y],++Map[nxtx][nxty];
ant[i].lastx=x,ant[i].lasty=y;
ant[i].x=nxtx,ant[i].y=nxty;
break;
}
}
if(!(ant[i].age%5)) {
for(int j=0; j<4; ++j) {
++dir;
if(dir==4) dir=0;
if(move[dir]) {
int nxtx=x+dx[dir],nxty=y+dy[dir];
--Map[x][y];
++Map[nxtx][nxty];
ant[i].lastx=x,ant[i].lasty=y;
ant[i].x=nxtx,ant[i].y=nxty;
break;
}
}
}
}
}
int len(ANT a,GUN b) {return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
int get_goal(int x) {
int goal=0,Min=0x3f3f3f3f;
if(cake&&len(ant[cake],gun[x])<=r*r) return cake;
for(int now,i=1; i<=antcnt; ++i) {
now=len(ant[i],gun[x]);
if(now<=r*r&&now<Min) Min=now,goal=i;
} return goal;
}
bool canhit(ANT a,GUN b,ANT c) {
Point A=Point(b.x,b.y);
Point B=Point(c.x,c.y);
Point P=Point(a.x,a.y);
double dis=DisTS(P,A,B);
if (dcmp(dis-0.5)<=0) return 1;
else return 0;
}
void Attack() {
for(int goal=0,i=1; i<=s; ++i,goal=0) {
goal=get_goal(i);
if(!goal) continue;
for(int j=1; j<=antcnt; ++j) {
if(canhit(ant[j],gun[i],ant[goal])) ant[j].blood-=d;
}
}
}
int main() {
freopen("antbuster_ex.in","r",stdin);
freopen("antbuster_ex.out","w",stdout);
scanf("%d%d",&n,&m);
scanf("%d%d%d",&s,&d,&r);
for(int i=1; i<=s; ++i) scanf("%d%d",&gun[i].x,&gun[i].y),Map[gun[i].x][gun[i].y]=-1;
scanf("%d",&t);
qx[0]=1; for(int i=1; i<=t; ++i) qx[i]=qx[i-1]*1.1;
for(T=1; T<=t; ++T) {
Birth();
Add_Information();
Move();
Carry();
Attack();
CheckDeath();
if(End=Check_end()) break;
Change();
}
if(End) printf("Game over after %d seconds\n%d\n",T,antcnt);
else printf("The game is going on\n%d\n",antcnt);
for(int i=1; i<=antcnt; ++i) printf("%d %d %d %d %d\n",ant[i].age-1,ant[i].level,ant[i].blood,ant[i].x,ant[i].y);
return 0;
}